2
\$\begingroup\$

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array.

  1. Solves it in linear time using a left to right pass of the array
  2. Solves it in linear time using a right to left pass of the array
  3. Solves it using divide and conquer in time \$Θ(n \log n)\$
  4. Solves it in time \$Θ(n^2)\$

At the start the right most element will always be a leader. If an element is greater than our current_max, it will a leader. Add this element to leaders. Set current_max to this element and carry on leftward. Time complexity would be \$O(n)\$.

Can you give an algorithm for another way or better way to find leader in an array?

#include <iostream>
using namespace std;

/* C++ Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
    int max_from_right =  arr[size-1];

    /* Rightmost element is always leader */
    cout << max_from_right << " ";

    for (int i = size-2; i >= 0; i--)
    {
        if (max_from_right < arr[i])
        {           
            max_from_right = arr[i];
            cout << max_from_right << " ";
        }
    }    
}

/* Driver program to test above function*/
int main()
{
    int arr[] = {16, 17, 4, 3, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    printLeaders(arr, n);
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ this is C++ code, not C, please remove the c tag. \$\endgroup\$ – user3629249 Jan 19 '16 at 14:04
  • \$\begingroup\$ I'm considering C , if you want to write code using C. \$\endgroup\$ – 1 0 Jan 19 '16 at 14:06
  • 1
    \$\begingroup\$ the right to left traversal is the fastest way I know of to accomplish the desired operation. \$\endgroup\$ – user3629249 Jan 19 '16 at 14:08
  • \$\begingroup\$ You should check that size > 0 before indexing into arr: an empty input will very likely make your code segfault. It is also a good idea to make size of type size_t, so that huge arrays don't break your code on 64 bit systems. \$\endgroup\$ – Jaime Jan 19 '16 at 15:54
  • 1
    \$\begingroup\$ @user3629249: The comment given with that deletion explained the reasoning. It had to do with lack of improvements mentioned. It doesn't matter if it still addressed a question. \$\endgroup\$ – Jamal Jan 19 '16 at 22:28
4
\$\begingroup\$

First off this is a C solution there is nothing inherently C++ about this code. You just seem to be using the output stream. We refer to this as kind of code (in the C++ community) as C with classes. Note this is not a good designation.

As C and C++ are completely different languages with different styles and idioms you should not write a piece of code for one and expect it to be good code in the other language. The fact that the compiler may compile it is just a historical artifact. You should remove one of the tags from question (Since it will not compile as C I suggest you remove the C tag).

Since the question is tagged C++ I will review your code as a C++ program and point out why it is badly designed.

Never do this:

using namespace std;

See: Why is “using namespace std;” considered bad practice?

Useless comments are worse then no comments.

/* C++ Function to print leaders in an array */
void printLeaders(int arr[], int size)

I don't need a comment to tell me this. The name of the function and its parameters are actually very well named. Restrict your comments to a description of why (the code describes how) and well named functions and variables describe what is happening.

C++ code prefers to use iterators it situations like this.

void printLeaders(int arr[], int size)

The problem here is that it is so easy to use this incorrectly. Arrays decay into pointers way to easily. If you use the iterator interface this will prevent this happening accidentally.

template<typename I>
void printLeaders(I begin, I end) {
    // Code
}

// Calling:
int arr[] = {16, 17, 4, 3, 5, 2};
printLeaders(std::begin(arr), std::end(arr));
// If you change the code now and accidentally cause the array to decay into a
// pointer then the compiler will generate a compile time error. The current
// code is way to susceptible to refactoring mistakes.

// Also it allows you to use any container that supports the iterator
// interface (which is all of them including built in array).

You have forgotten to validate your input.

    int max_from_right =  arr[size-1];

If the size is zero. Then this is undefined behavior.

I know you are printing here.
But that looks like for de-bugging.

        if (max_from_right < arr[i])
        {           
            max_from_right = arr[i];
            cout << max_from_right << " ";
        }

You could just use std::max() to simplify the code.

You should basically never use the built in array.

    int arr[] = {16, 17, 4, 3, 5, 2};

The container library contains several classes for storing a set of obejcts that are better. std::vector<int> for dynamically sized objects or std::array<int,size> for fixed size containers.

Built in arrays are hard to use correctly. Passing them by reference the syntax is non-trivial. They decay into pointers way to easily. Getting the size of an array is obnoxious as you have to remember to plant the correct division that is easy to mistype (with no compiler checking).

No need to return 0 at the end of main (its special).

    return 0;

Normally in C++ you leave out the return value to indicate that main can never fail. If you explicitly plant return 0 here it is an indication that it succeeds but also a hint there are other return paths that will fail (so I start looking for other return statements in main())

\$\endgroup\$
2
\$\begingroup\$

There could be an iterative solution:

#include <iostream>

This function takes a pointer of the array of integers n, remaining numbers to process num, maximum number on the right max, and if it is being called at start isStart.

void getLeaders(const int *n, int nums, int max, bool isStart = 0) {  

If no numbers remain to process, then quit.

    if (nums < 0) return;   

If I have just started, or we get a value higher than what we have got till now, then this is our leader:

    if (isStart || *n > max) {
        max = *n;
        cout << *n << " ";
    }

Now process the next number on the left, with new maximum:

    return getLeaders(--n, nums-1, max);
}

Caller:

int main() {
    int n[] = {12,10,9,5,3,4,1};
    int nn = sizeof(n)/sizeof(n[0]);

    getLeaders(n+nn-1, nn, 0, 1);    
    return 1;
}
\$\endgroup\$
  • \$\begingroup\$ Prefer sizeof(n[0]) over sizeof(int). If the type of n changes then your code will break as it is currently designed. You should design your code to be resistant to this simple type of changes. eg. we change n to long n[] = {/*Stuff*/}; \$\endgroup\$ – Martin York Jan 19 '16 at 18:36
  • 1
    \$\begingroup\$ You have provided an alternate solution, but you haven't reviewed the code. Please explain how your solution is better than the original code, so that we may learn from your thought process. \$\endgroup\$ – 200_success Jan 19 '16 at 19:17
1
\$\begingroup\$

I think I'd do one of two things. I'd either use some existing algorithms to handle most of the job, or else implement the code as a generic algorithm itself (if it seemed at all likely that it was going to be reusable enough to justify doing so). Of course, the two aren't mutually exclusive--it's entirely possible to implement a generic algorithm in terms of other generic algorithms, and often useful to do so.

If we were going to just use generic algorithms, what we're doing is copying some elements from the input to an output if they meet a criteria. That sounds like std::copy_if (or std::remove_copy_if).

I'd also prefer to get the compiler to compute the size of the array for us instead of computing and passing it explicitly (or, pass iterators). Taking those into account, code could look something like this:

template <size_t size, class T>
void print_leaders(T(&arr)[size]) {
    auto leader = arr[size - 1];
    std::cout << leader << "\t";

    std::copy_if(std::rbegin(arr)+1, std::rend(arr),
        std::ostream_iterator<int>(std::cout, "\t"),
        [&](int i) { 
            bool ret = i > leader;
            if (ret)
                leader = i;
            return ret;
        });
}

This passes the size of the array and the type of elements in the array as template parameters, but still requires (for example) that the input be an array, not just something that provides an array-like interface (e.g., std::vector or std::deque). If we wanted to accommodate different container types, we could just pass a pair of iterators (or a range). If we were going to do that, we'd also probably want to use std::advance instead of std::rbegin(array)+1, so the code can work with iterators that don't provide random access (required for addition to work).

\$\endgroup\$
  • \$\begingroup\$ I think the use of lambdas here is overkill. A simple for() loop is trivial enough to write. \$\endgroup\$ – Martin York Jan 19 '16 at 18:39
  • \$\begingroup\$ Ahhh, Good point. Got carried away on that point. \$\endgroup\$ – Martin York Jan 19 '16 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.