algoadvance

Leetcode 1299. Replace Elements with Greatest Element on Right Side

Problem Statement

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

Clarifying Questions

  1. Q: What is the size range of the array?
    • A: The size of the array can be up to 10^4 elements.
  2. Q: What kind of values can the elements of the array hold?
    • A: The elements are integers ranging from -10^6 to 10^6.
  3. Q: Should the solution modify the array in-place?
    • A: Yes, the solution should modify the array in-place if possible.
  4. Q: Is it allowed to use extra space?
    • A: Ideally, the solution should use O(1) additional space apart from the input array itself.

Strategy

To solve this problem efficiently, we can traverse the array from right to left. By keeping track of the greatest element we have seen so far, we can replace each element with the maximum of the elements to its right:

  1. Initialize a variable to keep track of the greatest element seen so far, starting with -1 (since the last element should be replaced by -1).
  2. Traverse the array from right to left.
  3. For each element, store its value in a temporary variable.
  4. Update the current element to the greatest value seen so far.
  5. Update the greatest value seen so far to the maximum of the previous greatest value and the current value (from the temporary variable).

Code

Here’s the implementation in Java:

public class Solution {
    public void replaceElements(int[] arr) {
        // Initialize the greatest element as -1 (the replacement for the last element)
        int greatest = -1;
        
        // Traverse the array from right to left
        for (int i = arr.length - 1; i >= 0; i--) {
            // Temporarily store the current element
            int current = arr[i];
            // Replace current element with the greatest element seen so far
            arr[i] = greatest;
            // Update greatest element seen so far
            greatest = Math.max(greatest, current);
        }
    }
}

Time Complexity

This solution efficiently processes the array in a single pass with minimal additional space utilization.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI