Swift Coding Test Course, Stack and Queue

Problem Description

Given an array of integers arr, each element in the array is a non-negative integer. For each element, the task is to find the index of the first element to its right that is greater than itself, and create a new array with those indices. If there is no such element, store -1.

For example, if the array is [2, 1, 5, 3, 6, 4], the result will be [2, 1, 1, 1, -1, -1].

Approach to the Problem

This problem can be efficiently approached using a stack. By traversing the entire array only once, we can use the stack to solve the issues occurring on the right side of each element. This reduces the time complexity.

Algorithm Explanation

  1. Initialize an array result to store the results.
  2. Initialize a stack to store indices.
  3. Traverse the array from right to left.
    • If the current element is greater than the last element in the stack, pop elements from the stack and store values at the corresponding indices in the result array.
    • If the stack is empty, store -1 in the result array.
    • Add the current index to the stack.
  4. Return the final result array.

Code Implementation

func nextGreaterElement(arr: [Int]) -> [Int] {
        var result = Array(repeating: -1, count: arr.count)
        var stack: [Int] = []

        for i in (0..

Code Explanation

The code is structured as follows:

  • result: The result array is initialized to -1.
  • stack: The stack is initialized to store indices.
  • reversed: The array is traversed in reverse. This is done to compare each element with the elements to its right.
  • Using the pop operation from the stack to find elements greater than itself.
  • Updating the result array with the found index and adding the current index to the stack.

Time Complexity

This algorithm adds and removes each element from the stack only once, thus the time complexity is O(n). This is very efficient.

Conclusion

In this lecture, we learned how to efficiently solve the given problem using a stack. Stacks and queues are data structures that often appear in various coding interview problems. Therefore, understanding and utilizing these two data structures is essential.

By solving this problem, try to develop your own problem-solving approach and attempt various problems. More problems related to stacks and queues will be covered later.