Kotlin Coding Test Course, Finding the Next Greater Number

One of the problems that frequently appears in programming and algorithm tests is the ‘Next Greater Element’ problem. This problem requires an understanding of efficient algorithms and data structures, and it can be very useful in various real programming situations.

Problem Description

Problem: For each number in a given integer array, find the next greater number that appears to the right, and output that number. If it does not exist, output -1.

Input Format

• The first line contains a natural number N (1 ≤ N ≤ 1,000,000).
• The second line contains an array of N integers. The values are from 1 to 1,000,000.

Output Format

Output an array consisting of N integers representing the next greater elements for each number.

Example

Input

    4
    3 5 2 7
    

Output

    5 7 -1 -1
    

How to Solve the Problem

To solve this problem, we will utilize the stack data structure. A stack is a LIFO (Last In, First Out) structure, which means that the last element added is the first one to be removed. By using this structure, we can efficiently find the next greater element for each element.

Algorithm Explanation

1. Create a stack. This stack will store indices.
2. Traverse the given array.
3. If the current number is greater than the number at the top of the stack, pop indices from the stack and store the current number as the next greater element at those indices.
4. Add the current index to the stack.
5. After repeating this process for all numbers, any remaining indices in the stack indicate there is no next greater element, so store -1 for those indices.

Kotlin Code Implementation

fun findNextGreater(nums: IntArray): IntArray {
    val result = IntArray(nums.size) { -1 }  // Initialize result array
    val stack = mutableListOf()  // Create stack

    for (i in nums.indices) {
        // While stack is not empty and current number is greater than the top of the stack
        while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
            result[stack.removeAt(stack.size - 1)] = nums[i]  // Store next greater element
        }
        stack.add(i)  // Add current index
    }
    
    return result
}

fun main() {
    val inputArray = intArrayOf(3, 5, 2, 7)
    val result = findNextGreater(inputArray)

    print(result.joinToString(" "))  // Print result
}
    

Code Explanation

The code above is an implementation of the algorithm to find the next greater element in Kotlin. Let's examine the main parts.

1. Initializing the Result Array

The result array is intended to store the next greater elements. It is initialized to -1 by default. This is to handle cases where there is no next greater element.

2. Searching Using a Stack

When the top index of the stack points to a value that is less than the current index i, we pop that index and assign the current number to the result array at that index. This process helps us find the next greater element.

3. Final Result Output

After searching through all numbers, we output the final result array. The result is printed with the next greater elements for each number in the given array.

Performance Analysis

The time complexity of this method is O(N). It is efficient since each element is pushed and popped from the stack only once. The space complexity is O(N) because the stack and the result array are used, meaning the memory used is proportional to the input size.

Conclusion

Today we learned how to solve the Next Greater Element problem using Kotlin. I hope you have felt the importance of data structures and algorithms, and I encourage you to continue practicing to enhance your algorithm problem-solving skills.