Array Leaders | Optimal Solution in Python

Given an array arr[] of size n, an element is called an Array Leaders if it is greater than or equal to every element on its right.
Your task is to return all leaders in their original left-to-right order.

Here’s the [Problem Link] to begin with.

Quick Examples

The naive idea would be to check every element against everything to its right (O(n²)), but we can do better in one backward pass.

Optimal Solution (Right-to-Left Scan)

Intuition and Approach

• Sweeping from the right keeps track of the maximum value seen so far (maxi).
• Every time the current element arr[i] is ≥ maxi, it means nothing to its right is larger, so arr[i] is a leader.
• Update maxi whenever a new leader is found.
• Collect leaders in a list while moving right → left, then reverse that list to restore left-to-right order.

This achieves the goal in one linear pass with constant extra space.

Code Implementation

class Solution:
    def leaders(self, arr):
        n = len(arr)
        maxi = float("-inf")   # holds the greatest element seen so far (to the right)
        result = []            # stores leaders found during the scan (right ➜ left)

        # Traverse array from right to left
        for i in range(n - 1, -1, -1):
            if arr[i] >= maxi:
                result.append(arr[i])      # current element is a leader
                maxi = max(maxi, arr[i])   # update the running maximum

        result.reverse()        # restore original ordering
        return result

Code Explanation

1. Initialization
   • maxi starts at negative infinity so that the right-most element is always a leader.
2. Backward Scan
   • At each position i, compare arr[i] with maxi.
   • If arr[i] is ≥ maxi, no larger element exists to its right → it’s a leader.
   • Push it into result and update maxi.
3. Result Reversal
   • Leaders were gathered right-to-left; a single reverse() restores left-to-right order.

Dry Run (Input [16, 17, 4, 3, 5, 2])

After reversal → [17, 5, 2], which matches the expected leaders.

Time & Space Complexity

• Time: O(n) – single traversal of the array.
• Space: O(1) extra (the result list holds at most n leaders, but no auxiliary arrays proportional to n are created aside from output).

Precise: O(n) for scanning + O(n) in worst-case leaders list → effectively still O(n) total.

Conclusion

The right-to-left scan leverages a running maximum to identify leaders in just one pass. This elegant approach highlights a common pattern in array problems: processing from the end can turn seemingly quadratic checks into linear-time solutions. Master it and similar “suffix maximum” tricks will feel natural in future challenges!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.