Print largest values of a list in the same order without making a new list

Question

Here I have a list

[9,1,2,11,8]

I need to print the top 3 in this list like,

[9,11,8]

It is easy to sort and take top values and loop over the same copied list to find the top values in the given order But I shouldn't use new list for this task. Is that possible?

Answer 1

def k_largest(iterable, k=3):
    it = iter(iterable)
    result = [next(it) for _ in range(k)] # O(k) space
    r_min = min(result)
    for elem in it:
        if elem > r_min:
            result.remove(r_min)  # O(n*k) time
            result.append(elem)
            r_min = min(result)
    return result

First value wins in case of tie. If you wanted last value wins instead, simply change the > into >=.

This is a good approach for large data and small selects, i.e. where n >> k with n being the length of input and k being the number selected. In this case, the k term is insignificant so the approach is O(n) time-complexity, favorable to O(n log n) of sorting-based approaches. If k is large, this will no longer be a good solution. You should look at maintaining a sorted result set, bisecting it for insertions, and perhaps using quickselect to find the maxima.

Another option which has simpler code is available using Python stdlib's heapq.nlargest, though it may generally be slower in practice:

import heapq
from operator import itemgetter

def k_largest_heap(iterable, k=3):
    ks = heapq.nlargest(k, enumerate(iterable), key=itemgetter(1))
    return [k for i, k in sorted(ks)]

I think this is O(n log(k)), although admittedly I'm reaching the edges of my knowledge here.

Some timings with a list of 10,000 integers:

from random import randint
nums =  [randint(1, 10000) for _ in range(10000)]
%timeit k_largest(nums)
# 331 µs ± 4.69 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit k_largest_heap(nums)
# 1.79 ms ± 27.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit top_three(nums)
# 1.39 ms ± 16.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Note: top_three implementation is the solution from user Delirious Lettuce here.

Answer 2

I would modify a select-sort to capture (n) as MAX instead of just one. and instead of running n2, just go thru the list once.

so [9,1,2,11,8]

you'd initialize with a MAX list [0,0,0] then loop thru your list plucking things that are bigger than MAX

1. [9,0,0]
2. [9,1,0]
3. [9,1,2]
4. [9,11,2]
5. [9,11,8]

the trickiest part is step 4 where you need to decide to keep 9, and 2 and replace 1 with 11.

Answer 3

You could also implement a wrapper class for your list. Have private data members (In your case 3) for the largest values in the list. Update these variables upon performing insertion and deletion.

Answer 4

I tried to create a sample program based on the input and the output you have asked for. I thought of giving a try. Please feel free to optimize or provide feedback. I tried to explain steps in the code itself. Thank you.

package com.test;

import java.util.ArrayList;
import java.util.List;

public class ArrangeList {
    public static void main(String[] args) {
        List<Integer> givenList = new ArrayList<>();
        givenList.add(9);
        givenList.add(1);
        givenList.add(2);
        givenList.add(11);
        givenList.add(8);

        int currentIndex = 0; //gives the current index
        while (givenList.size() != 3) {
            int nextIndex = currentIndex + 1; //gives you the next index 
            int currentValue = givenList.get(currentIndex); //gives you the current value for the current index 
            int nextValue = givenList.get(nextIndex); //gives you the next value for the next index

            if (nextValue < currentValue) { //check if the next value is greater than current value. If true, then remove the next value from the list
                givenList.remove(nextIndex);
            } else {
                currentIndex++; //increment the index if you if the current value is greater than the upcoming value from the list
            }

        }
        System.out.println(givenList); //prints the values stored in the list

    }
}

The output after execution of the program is:

[9, 11, 8]

Answer 5

EDIT:

I'm curious as to why I'm being downvoted. The solution by @wim willingly ignores the restriction in the original question about "without making a new list". The only response was to temporarily change it to a deque in an odd attempt to get around that restriction. Currently, this is the only answer which adheres to all of OPs requirements (listed below as two separate comments).

---

Print largest values of a list in the same order without making a new list

I need to print the top 3 in this list like

This answer assumes that the number is always three for how many of the top numbers you need to extract, in their original order. If that is the case, this answer seems to be O(n) time and O(1) space.

def top_three(nums):
    if len(nums) <= 3:
        return nums

    a = b = c = float('-inf')
    dex_a = dex_b = dex_c = None
    for i, num in enumerate(nums):
        if num > a and num > b and num > c:
            a, b, c = num, a, b
            dex_a, dex_b, dex_c = i, dex_a, dex_b
        elif num > b and num > c:
            b, c = num, b
            dex_b, dex_c = i, dex_b
        elif num > c:
            c = num
            dex_c = i

    if dex_a < dex_b < dex_c:
        print(a, b, c)
    elif dex_a < dex_c < dex_b:
        print(a, c, b)
    elif dex_b < dex_a < dex_c:
        print(b, a, c)
    elif dex_b < dex_c < dex_a:
        print(b, c, a)
    elif dex_c < dex_a < dex_b:
        print(c, a, b)
    elif dex_c < dex_b < dex_a:
        print(c, b, a)

Tests:

In[3]: top_three([9, 1, 2, 11, 8])
9 11 8
In[4]: top_three([9, 1, 2, 11, 8, 9])
9 11 9
In[5]: top_three([3, 3, 1, 0, 4, 3, 2, 5])
3 4 5