[AlgoMastery]
Topics›Array›Next Greater Element
📖

Next Greater Element

Array
~20 min read
5 practice problems

Overview

Next Greater Element problems involve finding the first element to the right (or left) that is greater (or smaller) than the current element. These problems are efficiently solved using monotonic stack, which maintains elements in sorted order.

The key insight: use a stack to store elements in decreasing order. When a larger element is found, it becomes the "next greater" for elements in the stack.

Next greater element problems are particularly useful for:

  • Finding next/previous greater/smaller elements
  • Circular array variations
  • Range queries
  • Stock span problems
  • Building relationships between elements

Pattern 1: Next Greater Element I

Find next greater element for each element in nums1 within nums2.

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const nextGreater = new Map<number, number>();
  const stack: number[] = [];
  
  // Build next greater map for nums2
  for (const num of nums2) {
    while (stack.length > 0 && num > stack[stack.length - 1]) {
      nextGreater.set(stack.pop()!, num);
    }
    stack.push(num);
  }
  
  // Query for nums1
  return nums1.map(num => nextGreater.get(num) || -1);
}

Time: O(n + m), Space: O(n + m)

Explanation: Stack maintains decreasing order. When larger element found, it's next greater for popped elements.

Pattern 2: Next Greater Element II (Circular)

Find next greater element in circular array.

function nextGreaterElements(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = [];
  
  // Process array twice for circular
  for (let i = 0; i < n * 2; i++) {
    const index = i % n;
    
    while (stack.length > 0 && nums[index] > nums[stack[stack.length - 1]]) {
      const top = stack.pop()!;
      result[top] = nums[index];
    }
    
    if (i < n) {
      stack.push(index);
    }
  }
  
  return result;
}

Time: O(n), Space: O(n)

Key insight: Process array twice to handle circular nature.

Pattern 3: Next Greater Element III

Find smallest integer greater than n with same digits.

function nextGreaterElementIII(n: number): number {
  const digits = n.toString().split('').map(Number);
  
  // Find first decreasing digit from right
  let i = digits.length - 2;
  while (i >= 0 && digits[i] >= digits[i + 1]) {
    i--;
  }
  
  if (i < 0) return -1; // No greater number possible
  
  // Find smallest digit greater than digits[i] from right
  let j = digits.length - 1;
  while (digits[j] <= digits[i]) {
    j--;
  }
  
  // Swap
  [digits[i], digits[j]] = [digits[j], digits[i]];
  
  // Reverse suffix
  let left = i + 1;
  let right = digits.length - 1;
  while (left < right) {
    [digits[left], digits[right]] = [digits[right], digits[left]];
    left++;
    right--;
  }
  
  const result = parseInt(digits.join(''));
  return result > 2147483647 ? -1 : result;
}

Time: O(d) where d is number of digits, Space: O(d)

Algorithm: Similar to next permutation.

Pattern 4: Next Smaller Element

Find next smaller element for each position.

function nextSmallerElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Pop while current element is smaller than stack top
    while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 5: Previous Greater Element

Find previous greater element for each position.

function previousGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  
  // Process from right to left
  for (let i = nums.length - 1; i >= 0; i--) {
    // Pop while current element is greater than stack top
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 6: Previous Smaller Element

Find previous smaller element for each position.

function previousSmallerElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  
  // Process from right to left
  for (let i = nums.length - 1; i >= 0; i--) {
    // Pop while current element is smaller than stack top
    while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 7: Daily Temperatures

Find days until warmer temperature.

function dailyTemperatures(temperatures: number[]): number[] {
  const result = new Array(temperatures.length).fill(0);
  const stack: number[] = [];
  
  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = i - index;
    }
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Variation: Return indices instead of days.

Pattern 8: Next Greater Node in Linked List

Find next greater node value for each node.

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number) {
    this.val = val;
    this.next = null;
  }
}

function nextLargerNodes(head: ListNode | null): number[] {
  const values: number[] = [];
  let current = head;
  
  // Convert to array
  while (current) {
    values.push(current.val);
    current = current.next;
  }
  
  const result = new Array(values.length).fill(0);
  const stack: number[] = [];
  
  for (let i = 0; i < values.length; i++) {
    while (stack.length > 0 && values[i] > values[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = values[i];
    }
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 9: Buildings with Ocean View

Find buildings that have ocean view (no taller building to right).

function findBuildings(heights: number[]): number[] {
  const result: number[] = [];
  let maxHeight = 0;
  
  // Process from right to left
  for (let i = heights.length - 1; i >= 0; i--) {
    if (heights[i] > maxHeight) {
      result.push(i);
      maxHeight = heights[i];
    }
  }
  
  return result.reverse();
}

// Using stack
function findBuildingsStack(heights: number[]): number[] {
  const stack: number[] = [];
  
  for (let i = 0; i < heights.length; i++) {
    // Remove buildings blocked by current
    while (stack.length > 0 && heights[stack[stack.length - 1]] <= heights[i]) {
      stack.pop();
    }
    stack.push(i);
  }
  
  return stack;
}

Time: O(n), Space: O(n)

Pattern 10: Next Greater Element with Distance

Find next greater element and its distance.

function nextGreaterElementWithDistance(nums: number[]): Array<[number, number]> {
  const result: Array<[number, number]> = [];
  const stack: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = [nums[i], i - index];
    }
    stack.push(i);
  }
  
  // Remaining elements have no greater element
  while (stack.length > 0) {
    const index = stack.pop()!;
    result[index] = [-1, -1];
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 11: Count Next Greater Elements

Count how many next greater elements exist.

function countNextGreaterElements(nums: number[]): number[] {
  const result = new Array(nums.length).fill(0);
  const stack: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    let count = 0;
    
    // Count and remove elements smaller than current
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      stack.pop();
      count++;
    }
    
    result[i] = count;
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 12: Next Greater Frequency Element

Find next element with greater frequency.

function nextGreaterFrequency(nums: number[]): number[] {
  // Count frequencies
  const freq = new Map<number, number>();
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    const currentFreq = freq.get(nums[i])!;
    
    while (stack.length > 0) {
      const topIndex = stack[stack.length - 1];
      const topFreq = freq.get(nums[topIndex])!;
      
      if (currentFreq > topFreq) {
        result[topIndex] = nums[i];
        stack.pop();
      } else {
        break;
      }
    }
    
    stack.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

When to Use Next Greater Element Techniques

Use next greater element techniques when:

  • Problem asks for next/previous greater/smaller element
  • Need to find relationships between elements
  • Circular array variations
  • Range queries with constraints
  • Stock span or similar problems
  • Building relationships in sequences

Key insight: Monotonic stack maintains order, enabling efficient lookups.

Template (Next Greater Element)

function nextGreaterElementTemplate(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = []; // Store indices
  
  for (let i = 0; i < nums.length; i++) {
    // Pop while current element is greater than stack top
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }
    stack.push(i);
  }
  
  return result;
}

Template (Next Smaller Element)

function nextSmallerElementTemplate(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Pop while current element is smaller than stack top
    while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
      const index = stack.pop()!;
      result[index] = nums[i];
    }
    stack.push(i);
  }
  
  return result;
}

Time and Space Complexity Summary

  • Next greater element: O(n) time, O(n) space
  • Circular array: O(n) time, O(n) space
  • Previous greater: O(n) time, O(n) space
  • Daily temperatures: O(n) time, O(n) space
  • Next greater frequency: O(n) time, O(n) space

Practice Tips

  1. Choose direction - Left to right for next, right to left for previous
  2. Store indices - Usually store indices, not values
  3. Monotonic order - Maintain decreasing stack for next greater
  4. Circular arrays - Process array twice
  5. Handle remaining - Set -1 for elements without greater element

Common Mistakes

  1. Wrong order - Using increasing when need decreasing
  2. Index confusion - Storing values instead of indices
  3. Not handling remaining - Forgetting to set -1 for unprocessed
  4. Circular arrays - Not processing twice
  5. Boundary errors - Off-by-one in index calculations

Related Concepts

  • Monotonic Stack - Core technique
  • Stack - Data structure used
  • Circular Array - Common variation
  • Two Pointers - Alternative for some problems

Next greater element problems are common in interviews. Master monotonic stack technique, and you'll efficiently solve these relationship-finding problems in coding interviews.

← PreviousArray PartitioningNext →Trapping Rain Water