Leader Elements in Array in C

Summary: This C program identifies leader elements in an array. A leader is an element that is greater than all the elements to its right. The last element is always a leader by definition.

#include <stdio.h>

void findLeaders(int arr[], int n) {
    int leaders[n];  // Array to store leaders
    int count = 0;   // To keep track of the number of leaders
    int maxFromRight = arr[n - 1];  // Last element is always a leader

    // Store the rightmost leader
    leaders[count++] = maxFromRight;

    // Traverse the array from second last to the first element
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i] > maxFromRight) {
            maxFromRight = arr[i];  // Update maxFromRight
            leaders[count++] = maxFromRight;
        }
    }

    // Print leaders in correct order (reverse of the array)
    printf("Leaders: ");
    for (int i = count - 1; i >= 0; i--) {
        printf("%d ", leaders[i]);
    }
    printf("\n");
}

int main() {
    int n;

    // Get the number of elements in the array
    printf("Enter the number of elements: ");
    scanf("%d", &n);

    // Check constraints
    if (n < 1 || n > 100) {
        printf("Invalid number of elements! Please enter a value between 1 and 100.\n");
        return 1;
    }

    int arr[n];
    
    // Get the elements of the array
    printf("Enter the elements: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Find and print leaders
    findLeaders(arr, n);

    return 0;
}

Explanation:

Program Overview:

This program identifies leader elements in an array and prints them. A leader is an element that is greater than all elements to its right. The logic involves traversing the array from right to left and comparing each element with the maximum element encountered so far.

Function - findLeaders():

The function findLeaders() takes two parameters:

• arr[]: The array of integers.
• n: The size of the array.

It identifies the leader elements and prints them in the correct order.

Logic to Identify Leaders:

1. Initialize the Rightmost Leader:
   • The last element is always a leader, so it is stored as the first leader in the leaders array.
   • maxFromRight keeps track of the maximum element encountered while traversing the array from right to left.
2. Traverse the Array from Right to Left:
   • The loop runs from the second last element to the first element.
   • Each element is compared with maxFromRight.
3. Update Maximum and Store Leaders:
   • If the current element is greater than maxFromRight, it is considered a leader.
   • The element is stored in the leaders array and maxFromRight is updated to this element.
4. Print Leaders in Correct Order:
   • Leaders are collected in reverse order, so a second loop prints them in the correct order.

Main Function Workflow:

1. Input Size and Validation:
   • The user inputs the size of the array, and a validation check ensures it falls within the valid range of 1 to 100.
2. Input Array Elements:
   • The user then provides the elements of the array.
   • A loop reads the elements and stores them in arr[].
3. Call findLeaders() to Identify and Print Leaders:
   • The findLeaders() function is called with the array and its size.
   • The identified leaders are printed in the correct order.

Edge Cases and Error Handling:

• Single Element Array: If the array contains only one element, that element is the leader.
• All Elements in Decreasing Order: If the elements are in decreasing order, all elements are leaders.
• All Elements Equal: If all elements are the same, only the last element is printed as a leader.

Time Complexity:

• Best Case: O(n), since the array is traversed once from right to left.
• Worst Case: O(n) for any input size.

Space Complexity:

• Space complexity is O(n) as the leader elements are stored in an additional array.