{"post":"

Leaders in an array Problem

PROBLEM: Print all the LEADERS in the array. An element is a leader if it is greater than the elements to its right in the array.

Input: [32, 2, 4, 2, 5, 17, 24, 22]

Output: [32, 34, 22]

# Brute Force

Pseudo Code:

We start a loop and iterate till the second last element.
Inside another loop, we iterate over elements to its right( to the last index) to check if it is a leader
If it is greater than all elements, we mark it as a leader.
The rightmost is added after the loop ends.

Code:

#include <iostream>\nusing namespace std;\nvoid printLeader(int arr[], int size)\n{\nfor (int iterator = 0; iterator< size; iterator++)\n{\nint innerIterator;
\n\tfor (innerIterator = iterator + 1; innerIterator &lt; size; innerIterator++)\n\t{\n\t\tif (arr[iterator] &lt;= arr[innerIterator])\n\t\t\tbreak;\n\t}\n\n\tif (innerIterator == size)\n\t\tcout &lt;&lt; arr[iterator] &lt;&lt; \" \";\n}\n
\n}
\nint main()\n{\nint arr[] = { 32, 2, 4, 2, 5, 17, 24, 22 };\ncout << \"Leaders are { \";\nprintLeader(arr, 8);\ncout << \"}\";\nreturn 0;\n}

Output:

Leaders are { 32, 24, 22 }

Time Complexity: O(N*N)

Space Complexity: O(1)

# Optimized Approach

Pseudo Code:

We start a loop from the right.
We keep checking the max value. As soon as a max is found, print it.
End.

Code:

#include <iostream>\nusing namespace std;\nvoid printLeadersOptimized(int arr[], int size)
\n{\nint maxRight = arr[size - 1];\ncout << maxRight << \" \";\nfor (int iterator = size - 2; iterator >= 0; iterator--)\n{\nif (maxRight < arr[iterator])\n{\nmaxRight = arr[iterator];\ncout << maxRight << \" \";\n}\n}\n}
\nint main()\n{\nint arr[] = { 32, 2, 4, 2, 5, 17, 24, 22 };\ncout << \"Leaders are { \";\nprintLeadersOptimized(arr, 8);\ncout << \"}\";\nreturn 0;\n}

Output:

Leaders are { 32, 24, 22 }

Time Complexity: O(N)

Space Complexity: O(1)

\n","title":"Leaders in an array","authorDetails":{"name":"Anshuman Raina","slug":"anshuman-raina"},"seo":{"title":"Leaders in an array"},"description":"Leaders in an array Problem in C++. Print all the LEADERS in the array. An element is a leader if it is greater than the elements to its right in the array.","slug":"leaders-in-an-array-problem/","articleId":"636a83447bb1ce5072622b7b","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}