Broad Network


Leader for app.codility.com/programmers Explained in C

Category of Article : Technology | Computers and Software | Algorithm

By: Chrysanthus Date Published: 5 Jul 2025

Consider a sequence a0, a1 , . . . , an-1 . The leader of this sequence is the element whose
value occurs more than n/2 times.

Sequence

a0

a1

a2

a2

a4

a5

a6

Elements

6

8

4

6

8

6

6

Index

0

1

2

3

4

5

6


In the table the leader is highlighted in gray. It is possible to have a list without any leader. Notice that the sequence can have at most one leader. This is because, if there are two or more leaders, none of such a supposed leader would occur more than n/2 times for the whole list. By definition, a leader occurs more than n/2 times for the whole list. 

The leader may be found in different ways. Some methods are described in this lesson, starting with
trivially, slow ideas and ending with very creative, fast algorithms. The task is to find the value
of the leader of the sequence a0, a1 , . . . , an-1 , such that 0 <= ai <= 109 . If there is no leader,
the result should be -1.

Note:

Leader occurring more than n/2 times refers to C integer division. With integer division, 7/2 = 3½ = 3 and 6/2 = 3. Similarly, 5/2 = 2½ = 2 and 4/2 = 2. Similarly, 9/2 = 4½ = 4 and 8/2 = 4; and so on. That is, once a value occurs more than the integer division of n/2 times, then that is the leader. Again, with integer division, 7/2 is 3 and not 3½; 5/2 is 2 and not 2½; 9/2 is 4 and not 4½; and so on.

Solution with O(n2) Time Complexity

This uses two for-loops, with one nested in the other. The outer for-loop chooses an element. The inner for-loop runs through all the elements in the list, to see if the element chosen by the outer for-loop occurs more than n/2 times. The outer for-loop begins by choosing the first element, then the second element, then the third, until the last element. The program is:

    #include <stdio.h>

    int slowLeader(int A[], int n) {
        int leader = -1;
        
        for (int i=0; i<n; i++) {
            int candidate = A[i];
            int count = 0;
            for (int j=0; j<n; j++) {
                if (A[j] == candidate)
                    count += 1;
                if (count > n/2) {
                    leader = candidate;
                    break;
                }
            }
            if (count > n/2)
                break;
        }
        
        return leader;
    }


    int main(int argc, char **argv)
    {
        int A[] = {6, 8, 4, 6, 8 ,6, 6};
        int n = sizeof(A)/sizeof(A[0]);    //divide size of array by size of one (first) element
        int ret = slowLeader(A, n);
        
        printf("%i\n", ret);

        return 0;
    }

The output is 6.

Why the break Instructions? - Imagine that the list has a leader and this leader value forms the first elements in the list, then as soon as it is detected, these for-loops should break-off avoiding unnecessary iterations, up to n2 times. However, the above for-loops constitute O(n2) times in time complexity parlance. The maximum possible number of iterations (operations) is always quoted for time complexity.

Solution with O(n.log(n) + n) time complexity

If the list is first sorted in n.log2n time, and if the list has a leader, then the leader value will occur at zero based index n/2 (integer division). Remember that the leader occurs in more than n/2 times (integer division). In the sorted list, the first element may not be the leader and the last element may also not be the leader. Also, sorting the list does not guarantee that the list has a leader.

After sorting, the value at index n/2 is assumed to be the leader; it is the candidate. In an additional maximum of n operations, the whole list has to be scanned to see if the candidate occurs more than n/2 times (integer division), to confirm that it is a leader. The following fastLeader() function illustrates this with the above list:
    #include <stdio.h>
    #include <stdlib.h>    //has qsort() 

        int compFn(const void *a, const void *b) {    //comparison function for qsort()
            int int_a = *((int *)a);
            int int_b = *((int *)b);
            return int_a - int_b;
        }

    int fastLeader(int A[], int n) {
        int leader = -1;
        
        qsort(A, n, sizeof(int), compFn);
        
        int candidate = A[n/2];
        int count = 0;
        
        for (int j=0; j<n; j++) {
            if (A[j] == candidate)
                count += 1;
            if (count > n/2) {
                leader = candidate;
                break;
            }
        }
        
        return leader;
    }


    int main(int argc, char **argv)
    {
        int A[] = {6, 8, 4, 6, 8 ,6, 6};
        int n = sizeof(A)/sizeof(A[0]);    //divide size of array by size of one (first) element
        int ret = fastLeader(A, n);
        
        printf("%i\n", ret);

        return 0;
    }
The output is 6. 

The C qsort() function from the stdlib.h header takes four arguments. The first is the name of the array to be sorted. The second is the number of elements in the array. The third is the size of each element in the array. The fourth is the name of the comparison function, without the parentheses. It is the responsibility of the programmer to define the comparison function.

The C qsort() function takes about n.log(n) time and the for-loop takes a maximum of n time (actually, not more than n/2 plus 1 time). The statements outside the for-loop of constant time, O(1) are not included in the determination of the overall time complexity. All the statements in the for-loop body, are together considered as one main operation.

Solution with O(n + n) Time Complexity

Consider the above given unsorted list again:

            6, 8, 4, 6, 8, 6, 6

Beginning from the first element (left), any next two elements that are not the same, are removed from the list. The two elements must not necessarily occur consecutively (see sorting example below). 6 and 8 above are not the same. If they are removed, the list will become:

            4, 6, 8, 6, 6

From the left again, if 4 and 6 are removed, the list will become:

            8 ,6, 6

From the left again, if 8 and 6 are removed, the list will become:

            6

which is the leader for the above list. However, with some other lists, this would not necessarily be the leader. It might just be the majority element and not the absolute majority element (above n/2). So 6 here is the candidate. Going through the list like this, takes O(n) operations. Another O(n) operations are needed to see if the candidate is the absolute majority element and not just the majority element. In other words, the original list has to be scanned to see if the candidate occurs more than n/2 times (integer division). 

The removing of pairs of different elements, in order to end at the candidate, can better be appreciated (learned) with the sorted list, though sorting is not involved in the algorithm, explained below. 

Removing Pairs of Different Elements, seen with a Sorted List

The following is a sorted list, from above:

            4, 6, 6, 6, 6 ,8, 8

From the left, if 4 and 6 that are different are removed, the remaining list is:

            6, 6, 6, 8, 8

The next two 6 's are the same; they are not removed.

If the last 6 and the first 8 (from the left) that are different are removed, the list becomes:

            6, 6, 8

Removing the last 6 here and the remaining 8, leads to a remaining list of:

            6

Note that the 6 and 8 removed are not consecutive elements originally.

Now, after removal of different pairs of elements, if one element is remaining, then that is either the majority element or the absolute majority element. That is the candidate, and not necessarily the leader. In other words, that may be the majority element and not necessarily the absolute majority element (leader). If more than one element is remaining in the final reduced list, then such elements must be the same. If they are not the same, then pairs of different elements still have to be removed. 

The final list may have one or more than one element of the same value. The value is the candidate. It might be just a majority element or it might actually be the leader (absolute majority element). Another O(n) operations still has to be performed to know if the candidate occurs more than n/2 times (integer division).

So the time complexity is O(n+n). There should be no sorting here. The first n is for the removal of pairs of different elements. The second n is for the verification, if the candidate is truly the leader. 

In the following program of O(n+n) time complexity, the removing of elements is not achieved as bluntly as described above. Instead, a stack object is created, with one element, which is the first element copied from the given array. The rest of the elements of the given array are copied (push) to the new stack, one-by-one. The given array is not changed. 

As from the second element, copied and sent, each time sending occurs, the first element of the new vector is compared with the last element of the new vector. If they are different, first and last elements of the new vector are removed. If they are the same, then nothing is removed from the new vector; copying still takes place. At the end of the scanning of the given array, there may be at least one element in the stack. That element is the candidate. The candidate may be one or more of the same copies of the same value (in the stack). If the size of the stack ends as zero, then there is no candidate and no leader The states of the stack is best illustrated with a sorted list, though no sorting is involved with the O(n+n) algorithm. The sorted list from above is:

        4, 6, 6, 6, 6 ,8, 8

At the beginning, the stack is:

        4

When 6 is to be copied, the state of the stack is to become:

        4, 6

Since 4 and 6 are different, 4 is popped off (removed) from the stack and 6 does not go into the stack. At this point, the stack becomes empty. Next, 6 is copied to the stack, to have only 6, after comparing 6 with nothing in the stack. The fourth element at index 3 of the sorted given array, which is still 6, is copied to the stack, after comparison with 6 in the stack to be the same. The state (content) of the stack is now,

        6, 6

The fifth element at index 4 of the sorted given array, which is still 6, is copied to the stack, after comparison with the top 6 in the stack to be the same. The state (content) of the stack is now,

        6, 6, 6

The sixth element at index 5 of the sorted given array, which is 8, is to be copied to the stack. After comparison with the top 6 in the stack to be different, the top 6 in the stack is removed (popped off), and the 8 is not pushed onto the stack. The state (content) of the stack is now,

        6, 6

The seventh element at index 6 of the sorted given array, which is another 8, is to be copied to the stack. After comparison with the new top 6 in the stack to be different, the top 6 in the stack is removed (popped off), and the 8 is not pushed onto the stack. The state (content) of the stack is now,
 
        6

If at this point, the stack is empty, then no leader exists in the list. This also means that no majority element exists in the list. If the size of the stack at this point is one or more, then the value it contains is the candidate. There can be more than one occurrence of the candidate, at this stage, in the stack. Despite that, the next thing to do, is another O(n) operations, to verify if the candidate is the leader, occurring more than n/2 times in the given list (vector). The program for O(n+n) time is as follows. The C stack developed in the previous lesson is used here. A program with the solution function is as follows (read through the code and comments). Pay particular attention to the fastLeader() function definition and to the user code in the main() function.
    #include <stdio.h>
    #include <stdlib.h>
    
    struct Element {
        int value;
        struct Element *previous;
    }; 

    struct Stack {
        int size;
        struct Element *back;
 
        int (*top)();
        void (*push)(int);
        void (*pop)();
    } stack;

    int top() {
        if (stack.size > 0)    //stack has at least 1 element
            return stack.back->value;    //use -> to obtain value from a pointer   
        else
            printf("Error: No element to remove from stack!\n");
    }

    void push(int inte) {
        struct Element *element = malloc(sizeof(struct Element));    //declaring and creating the object, element
        if (element != 0) {    //check whether allocation of memory element was successful
            element->value = inte;
            if (stack.size == 0) {   //first element
               element->previous = 0;
               stack.back = element;
               stack.size = stack.size + 1;    //add 1 to size
            }
            else {
                element->previous = stack.back;    //previous points to previous element
                stack.back = element;    //stack points to new element
                stack.size = stack.size + 1;    //add 1 to size
            }
        }
        else {       
            printf("Error: New element could not be created!\n");
            exit(1);
        }
    }

    void pop() {
        if (stack.size > 0) {   //stack has at least 1 element
            struct Element *lastElement = stack.back;
            stack.back = lastElement->previous;    //point to previous element
            free(lastElement);    //free last (top) element from memory   
            stack.size = stack.size - 1;    //subtract 1 from size
        } 
        else {
            printf("Error: No element to remove from stack!\n");
            exit(1);
        }
    }

    int fastLeader(int A[], int n) {
        int leader = -1;
                
        stack.push(A[0]);
        
        // O(n) time
        for (int i=1; i<n; i++) {
            if (stack.size != 0 && stack.top() == A[i]) 
                stack.push(A[i]);
            else if (stack.size != 0)    //stack top and in-coming are different
                stack.pop();
            else                        //stack is empty
                stack.push(A[i]);
        }
        
        int candidate = -1;
        if (stack.size != 0)
            candidate = stack.top();
        else
            leader = -1;
        
        int count = 0;
        // Another O(n) time
        for (int i=0; i<n; i++) {
            if (A[i] == candidate)
                count += 1;
            if (count > n/2) {
                leader = candidate;
                break;
            }
        }
        
        return leader;
    }


    int main(int argc, char **argv)
    {
        //Assigning stack attributes and methods (functions)
        stack.size = 0;
        stack.top = top;
        stack.push = push;
        stack.pop = pop;

        //user code begins
        int A[] = {6, 8, 4, 6, 8 ,6, 6};
        int n = sizeof(A)/sizeof(A[0]);    //divide size of array by size of one (first) element
        int ret = fastLeader(A, n);
        printf("%i\n", ret);
        //user code begins

        return 0;
    }
The output is 6 as expected, but in O(n+n) time.

The condition, "stack.size != 0" should be seen as the comparison with an empty stack. Though the code for the stack is long, the pop(), top() and push() methods (functions) take O(1) time each (constant time).

Conclusion

The leader can be found in O(n2) time complexity, O(n.log(n) + n) time complexity and O(n+n) time complexity. The different approaches have been explained above. O(n+n) needs a stack.

The rest of the 17 lessons, with explanation of lessons, explanation of tasks, and explanation of solutions, can be found at (click): Explanations in C for the 17 Algorithm Lessons at https://app.codility.com/programmers with Problems and Solutions





Related Links

More Related Links

Cousins

NEXT

Comments