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
- Initialize an array
resultto store the results. - Initialize a stack to store indices.
- 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
-1in the result array. - Add the current index to the stack.
- 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..<arr.count).reversed() {="" while="" !stack.isempty="" &&="" arr[i]="" <="" arr[stack.last!]="" result[i]="stack.removeLast()" }="" if="" stack.isempty="" stack.append(i)="" return="" result="" let="" inputarray="[2," 1,="" 5,="" 3,="" 6,="" 4]="" output="nextGreaterElement(arr:" inputarray)="" print(output)="" result:="" [2,="" -1,="" -1]="" <="" code=""></arr.count).reversed()>
<h2>Code Explanation</h2>
<p>The code is structured as follows:</p>
<ul>
<li><code>result</code>: The result array is initialized to -1.</li>
<li><code>stack</code>: The stack is initialized to store indices.</li>
<li><code>reversed</code>: The array is traversed in reverse. This is done to compare each element with the elements to its right.</li>
<li>Using the pop operation from the stack to find elements greater than itself.</li>
<li>Updating the result array with the found index and adding the current index to the stack.</li>
</ul>
<h2>Time Complexity</h2>
<p>This algorithm adds and removes each element from the stack only once, thus the time complexity is <code>O(n)</code>. This is very efficient.</p>
<h2>Conclusion</h2>
<p>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.</p>
<p>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.</p>
<p></p>
<div id="jp-relatedposts" class="jp-relatedposts">
<h3 class="jp-relatedposts-headline"><em>관련</em></h3>
</div>