Next Greater Element

Next Greater Element – Understanding Element Relationships in Arrays

Problem Statement

Given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2, return an array of the next greater element for each element in nums1 corresponding to its position in nums2.

The next greater element of a number x in nums2 is the first greater number to the right of x in nums2. If it does not exist, return -1

Example

Input:
nums1 = [4,1,2]
nums2 = [1,3,4,2]

Output:
[-1, 3, -1]

Explanation:

  • For 4, there is no number greater than it to its right in nums2.

  • For 1, the next greater number is 3.

  • For 2, there is no greater number to the right.

Best Data Structure for the Job

To efficiently solve this problem, we use a stack in combination with a hash map. The stack helps us track elements in a decreasing order while scanning nums2 from right to left, enabling us to find the next greater element for each number efficiently. The hash map is then used to store and retrieve results quickly for each element in nums1.

Different Approaches

Approach 1: Brute Force (Nested Loops)

This method involves checking each element of nums1 by scanning nums2 to find its position, then iterating through the remaining elements in nums2 to find the next greater element.

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int idx = -1;
            // Find index of nums1[i] in nums2
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == nums1[i]) {
                    idx = j;
                    break;
                }
            }
            // Find next greater element
            int nge = -1;
            for (int k = idx + 1; k < nums2.length; k++) {
                if (nums2[k] > nums1[i]) {
                    nge = nums2[k];
                    break;
                }
            }
            ans[i] = nge;
        }
        return ans;
    }
}

This approach is easy to understand but not efficient for large input sizes.

Approach 2: Optimized Using Stack and Hash Map

Here, we precompute the next greater element for each number in nums2 using a monotonic decreasing stack. The results are stored in a hash map for fast lookup when constructing the output for nums1.

import java.util.*;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();

        for (int i = nums2.length - 1; i >= 0; i--) {
            int current = nums2[i];
            while (!stack.isEmpty() && stack.peek() <= current) {
                stack.pop();
            }
            map.put(current, stack.isEmpty() ? -1 : stack.peek());
            stack.push(current);
        }

        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.get(nums1[i]);
        }

        return result;
    }
}

This approach is significantly more efficient and scalable.

⚠️Common Mistakes and Pitfalls

  • Confusing search directions: The "next" greater element must be strictly to the right in nums2.

  • Not handling elements with no next greater: Always default to -1 if no greater value is found.

  • Using nested loops unnecessarily: This increases time complexity without adding value for large arrays.

  • Assuming elements repeat in nums2: The problem guarantees all elements are distinct, so no duplicates should be expected.

📊Time and Space Complexity Analysis

Approach      Time Complexity        Space Complexity
Brute Force        O(n1 × n2)        O(1)
Stack + Hash Map        O(n1 + n2)        O(n2)

🌍Real-world Applications

  • Stock analysis: Finding the next higher stock price after a specific day.

  • Data trend evaluation: Identifying the next spike or rise in a dataset.

  • System monitoring: Determining the next significant increase in performance metrics.


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Zero Array After Queries

Zero Array After Queries You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order . Example Input: nums = [ 1 , 0 , 1 ] queries = [[0, 2]] Output: true Explanation: We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0] . Best Data Structure for the Job We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum . It allows efficient range additions and helps track how many times each index is affected by the queries. Different Approaches Approach 1: Brute Force This naive method iterates over every index for every query and performs the decrement operations directly. class Solution {...
Read more