{"id":475,"date":"2025-06-29T20:41:32","date_gmt":"2025-06-29T15:11:32","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=475"},"modified":"2025-06-29T20:41:33","modified_gmt":"2025-06-29T15:11:33","slug":"array-leaders","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/array-leaders\/","title":{"rendered":"Array Leaders | Optimal Solution in Python"},"content":{"rendered":"\n

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

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Quick Examples<\/h3>\n\n\n\n
Input array<\/th>Leaders (output)<\/th>Why?<\/th><\/tr><\/thead>
[16, 17, 4, 3, 5, 2]<\/code><\/td>[17, 5, 2]<\/code><\/td>17<\/code> \u2265 4\u20262<\/code>, 5<\/code> \u2265 2<\/code>, last element 2<\/code> is always a leader<\/td><\/tr>
[7, 10, 4, 10, 6, 5, 2]<\/code><\/td>[10, 10, 6, 5, 2]<\/code><\/td>Scan from right: 2<\/code> (leader) \u2192 5<\/code> \u2265 2<\/code> \u2192 6<\/code> \u2265 5<\/code>\u2026<\/td><\/tr>
[1, 2, 3]<\/code><\/td>[3]<\/code><\/td>Only the right-most element meets the condition<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

The naive idea would be to check every element against everything to its right (O(n\u00b2)<\/code>), but we can do better in one backward pass.<\/p>\n\n\n\n

\n\n\n\n

Optimal Solution (Right-to-Left Scan)<\/h2>\n\n\n\n

Intuition and Approach<\/h3>\n\n\n\n