CODEWITHSUNDEEP
c++calgorithm
Anurag
Anurag

Reputation: 1016

Traversing an array to find the second largest element in linear time

Is there a way in linear time by which we can find which is the second largest element of an array ? Array elements can be positive, negative or zero. Elements can be repetitive. No STLs allowed. Python can be used.

Solution : Sort the array and take the second element but Sorting not allowed

Modification : By definition second largest element will be the one which is numerically smaller. Like if we have

Arr = {5,5,4,3,1} Then second largest is 4

Addition Lets say if i want to generalize the question to kth largest and complexity less than linear like nlogn, what can be the solution.

Upvotes: 2

Views: 2565

Answers (9)

Satinath Mondal
Satinath Mondal

Reputation: 1

// Second larger element and its position(s)
    int[] tab = { 12, 1, 21, 12, 8, 8, 1 };
    int[] tmp = Arrays.copyOf(tab, tab.length);
    int secMax = 0;
    Arrays.sort(tmp);
    secMax = tmp[tmp.length - 2];
    System.out.println(secMax);
    List<Integer> positions = new ArrayList<>();
    for (int i = 0; i < tab.length; i++) {
        if (tab[i] == secMax) {
            positions.add(i);
        }
    }
    System.out.println(positions);

Upvotes: 0

Andrew
Andrew

Reputation: 518

I think the other answers have not accounted for the fact that in an array like [0, 1, 1], the second largest is 0 (according to the updated problem definition). Furthermore, all mentions of quickselect are not O(n) but rather O(n^2) and are doing much more work than necessary (on top of which that is a sorting algorithm which the problem statement disallowed). Here is a very similar algorithm to Simone's but updated to return the second largest unique element:

def find_second(numbers):
    top = numbers[0]
    second = None

    for num in numbers[1:]:
        if second is None:
            if num < top: second = num
            elif num > top:
                second = top
                top = num
        else:
            if num > second:
                if num > top:
                    second = top
                    top = num
                elif num < top: second = num

    if second is not None: return second
    return top

if __name__ == '__main__':
    print "The second largest is %d" % find_second([1,2,3,4,4,5,5])

Upvotes: 0

Simone
Simone

Reputation: 11797

You can, this is the pseudo algorithm:

max = 2max = SMALLEST_INT_VALUE;

for element in v:
   if element > max:
      2max = max;
      max = element;

  else if element > 2max:
      2max = element;

2max is the value you are looking for.

The algorithm won't return a correct value for particular cases, such as an array where its elements are equal.

Upvotes: 7

CAFxX
CAFxX

Reputation: 30351

// assuming that v is the array and length is its length
int m1 = max(v[0], v[1]), m2 = min(v[0], v[1]);

for (int i=2; i<length; i++) {
  if (likely(m2 >= v[i]))
    continue;
  if (unlikely(m1 < v[i]))
    m2 = m1, m1 = v[i];
  else
    m2 = v[i];
}

The result you need is in m2 (likely and unlikely are macros defined as here for performance purposes, you can simply remove them if you don't need them).

Upvotes: 1

Tyler Crompton
Tyler Crompton

Reputation: 12672

Yep. You tagged this as C/C++ but you mentioned you could do it in Python. Anyway, here is the algorithm:

  1. Create the array (obviously).
  2. If the first item is greater than the second item, set first variable to the first item and second variable to second item. Otherwise, do vise-versa.
  3. Loop through all the items (except the first two).
  4. If the item from the array is greater than first variable, set second variable to first variable and first variable to the item. Else if the item is greater than second variable set second variable to the item.

The second variable is your answer.

list = [-1,6,9,2,0,2,8,10,8,-10]

if list[0] > list[1]:
        first = list[0]
        second = list[1]
else:
        first = list[1]
        second = list[0]

for i in range(2, len(list)):
        if list[i] > first:
                first, second = list[i], first
        elif list[i] > second:
                second = list[i]

print("First:", first)
print("Second:", second)

Upvotes: 1

Shankar Raju
Shankar Raju

Reputation: 4546

Pseudo code:

int max[2] = { array[0], array[1] }

if(max[1] < max[0]) swap them

for (int i = 2; i < array.length(); i++) {
  if(array[i] >= max[0]) max[1] = max[0]; max[0] = array[i]
  else if(array[i] >= max[1]) max[1] = array[i];
}

Now, max array contains the max 2 elements.

Upvotes: 2

Jhaliya - Praveen Sharma
Jhaliya - Praveen Sharma

Reputation: 31730

If you want a true O(n) algorithm, and want to find nth largest element in array then you should use quickselect (it's basically quicksort where you throw out the partition that you're not interested in), and the below is a great writeup, with the runtime analysis:

http://pine.cs.yale.edu/pinewiki/QuickSelect

Upvotes: 4

user684934
user684934

Reputation:

Go through the array, keeping 2 memory slots to record the 2 largest elements seen so far. Return the smaller of the two.

.... is there anything tricky about this question that I can't see?

Upvotes: 7

sharptooth
sharptooth

Reputation: 170559

  • create a temporary array of size 3,
  • copy first 3 elements there,
  • sort the temporary array,
  • replace the last one in the temporary array with the 4th element from the source array,
  • sort the temporary array,
  • replace the last one in the temporary array with the 5th element from the source array,
  • sort the temporary array,
  • etc.

Sorting array of size 3 is constant time and you do that once for each element of the source array, hence linear overall time.

Upvotes: 1

Related Questions