Next Greater Element I - Practice Coding Problems

Next Greater Element I - Problem

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Input & Output

Example 1 — Basic Case

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

› Output: [-1,3,-1]

💡 Note: For 4: appears at index 2 in nums2, no greater element to the right → -1. For 1: appears at index 0, next greater is 3 → 3. For 2: appears at index 3, no greater element to the right → -1.

Example 2 — All Elements Found

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

› Output: [3,-1]

💡 Note: For 2: appears at index 1 in nums2, next greater is 3 → 3. For 4: appears at index 3, no greater element to the right → -1.

Example 3 — Single Element

$ Input: nums1 = [1], nums2 = [1,2]

› Output: [2]

💡 Note: For 1: appears at index 0 in nums2, next greater is 2 → 2.

Constraints

1 ≤ nums1.length ≤ nums2.length ≤ 1000
0 ≤ nums1[i], nums2[i] ≤ 10⁴
All integers in nums1 and nums2 are unique
All the integers of nums1 also appear in nums2

Visualization

Tap to expand

Understanding the Visualization

Input

nums1 = [4,1,2] (queries), nums2 = [1,3,4,2] (search space)

Process

For each element in nums1, find its next greater element in nums2

Output

Return array with next greater elements or -1 if none exist

Key Takeaway

🎯 Key Insight: Use a monotonic stack to precompute next greater elements, then lookup queries in O(1) time

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is using a monotonic decreasing stack to efficiently find next greater elements in a single pass. The optimal approach builds a hash map of next greater elements using the stack, then performs O(1) lookups for each query. Time: O(m + n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack - Optimal Solution	O(m + n)	O(n)	Use a stack to find next greater elements in one pass, then lookup results
Brute Force - Linear Search	O(m × n)	O(1)	For each element in nums1, find it in nums2 and scan right for next greater element

Monotonic Stack - Optimal Solution — Algorithm Steps

Traverse nums2 with a monotonic stack
For each element, pop smaller elements and record their next greater
Push current element to stack
Lookup each nums1 element in the map

Visualization

Tap to expand

Step-by-Step Walkthrough

Process nums2

Use stack to track elements waiting for next greater

Build Map

Map each element to its next greater element

Lookup

Query map for each element in nums1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 10000

typedef struct {
    int key;
    int value;
} MapEntry;

typedef struct {
    MapEntry entries[MAX_SIZE];
    int size;
} HashMap;

void mapPut(HashMap* map, int key, int value) {
    for (int i = 0; i < map->size; i++) {
        if (map->entries[i].key == key) {
            map->entries[i].value = value;
            return;
        }
    }
    map->entries[map->size].key = key;
    map->entries[map->size].value = value;
    map->size++;
}

int mapGet(HashMap* map, int key, int defaultValue) {
    for (int i = 0; i < map->size; i++) {
        if (map->entries[i].key == key) {
            return map->entries[i].value;
        }
    }
    return defaultValue;
}

int* parseArray(char* line, int* size) {
    int* arr = malloc(1000 * sizeof(int));
    *size = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[(*size)++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    return arr;
}

void printArray(int* arr, int size) {
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(",");
    }
    printf("]\n");
}

int* solution(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    // Use a monotonic stack to find next greater elements
    HashMap nextGreater = {.size = 0};
    int stack[MAX_SIZE];
    int stackSize = 0;
    
    for (int i = 0; i < nums2Size; i++) {
        int num = nums2[i];
        // Pop elements smaller than current number
        while (stackSize > 0 && stack[stackSize - 1] < num) {
            mapPut(&nextGreater, stack[stackSize - 1], num);
            stackSize--;
        }
        stack[stackSize++] = num;
    }
    
    // Build result for nums1
    int* result = malloc(nums1Size * sizeof(int));
    for (int i = 0; i < nums1Size; i++) {
        result[i] = mapGet(&nextGreater, nums1[i], -1);
    }
    
    return result;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int size1, size2;
    int* nums1 = parseArray(line1, &size1);
    int* nums2 = parseArray(line2, &size2);
    
    int* result = solution(nums1, size1, nums2, size2);
    printArray(result, size1);
    
    free(nums1);
    free(nums2);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n)

Single pass through nums2 (n) plus lookup for each element in nums1 (m)

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n elements, stack stores up to n elements

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler