C# Coding Test Course, Creating an Ascending Sequence with a Stack

Problem Description

This is a problem to determine whether it is possible to create a sequence sorted in ascending order by using a stack from the given sequence. The input sequence should be able to be output in order from the smallest number. If it’s not possible, “NO” should be printed; if it is possible, “YES” should be printed.

Example Cases

Input: 5
Input Sequence: 5 1 2 3 4
Output: YES

Input: 7
Input Sequence: 1 2 5 3 4 6 7
Output: NO

Approach

This problem can be solved using the properties of a stack. A stack follows a Last In First Out (LIFO) structure, where the last element added is the first to be removed. Thus, to sort the sequence in ascending order, the input numbers need to be stored in the stack and removed only when necessary.

Step 1: Input Processing

First, the given sequence needs to be read. The length of the sequence and the elements of that sequence are received.

Step 2: Storing Elements in the Stack

While processing the input numbers sequentially, they need to be compared with the current number to output. We use the stack to store the current number so that it can be output starting from the smallest one.

Step 3: Output Condition Checking

If a number larger than the one we need to output is stacked, then it can no longer be retrieved, so “NO” is printed. After processing all elements, if possible, “YES” is printed.

C# Code Implementation

Below is the code implementing the algorithm explained above in C# language.


using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        Stack stack = new Stack();
        int current = 1;

        for (int i = 0; i < n; i++)
        {
            int num = int.Parse(Console.ReadLine());

            while (current <= num)
            {
                stack.Push(current);
                current++;
            }

            if (stack.Count == 0 || stack.Pop() != num)
            {
                Console.WriteLine("NO");
                return;
            }
        }

        Console.WriteLine("YES");
    }
}

Code Explanation

The C# code above works as follows:

int n = int.Parse(Console.ReadLine());
Takes the length of the sequence as input from the user.
Stack stack = new Stack();
Initializes the stack.
int current = 1;
Represents the current number to be outputted.
For each input number in a loop:

while (current <= num)
If the current number is less than or equal to the input number, add the current number to the stack and increase the current number.
if (stack.Count == 0 || stack.Pop() != num)
Pop the top number from the stack and compare it with the input number. If the stack is empty or they are different, print “NO”.

After processing all numbers, print “YES”.

Complexity Analysis

The time complexity of this algorithm is O(n). Each number is pushed and popped from the stack only once. The space complexity is also O(n) since in the worst case, all numbers might be stacked.

Conclusion

This problem is a typical one that can be solved using the properties of a stack. Such stack problems often appear in coding tests, so it’s important to have a good understanding of how stacks and queues operate. In this tutorial, we learned how to create a sequence in ascending order using a stack. Practicing these fundamental algorithms is essential for solving various problems.

Additional Practice Problems

Try solving other algorithm problems using stacks:

Parenthesis Balancing Problem
Postfix Notation Calculator

Reference Material

If you want to learn more algorithms, refer to the following materials: