Modifying the greatest elements of an array without changing their position?

Question

I'm trying to figure out how to modify the n greatest elements of an array without modifying their position. For example, suppose I have an array of ints {5, 2, 3, 4, 8, 9, 1, 3}; I want to add 1 to the two greatest elements, making the array {5, 2, 3, 4, 9, 10, 1, 3}.

All of the methods I can think of to go about doing this end up feeling clunky and unintuitive when I try to implement them, signaling to me that I'm not thinking about it correctly. For example, I could use a TreeMap with the values of the array as keys and their indices as values to find the greatest values, modify them, and then throw them back into the array, but then I would have have to implement my own Comparator to sort the TreeMap in reverse order(unless there's an easier way I'm not aware of?). I was also considering copying the contents of the array into a list, iterating through n times, each time finding the greatest element and its index, putting the modified greatest element back into the array at that index, removing the element from the list, and repeat, but that feels sloppy and inefficient to me.

Any suggestions as to how to approach this type of problem?

Jeff Paulsen · Accepted Answer · 2011-05-13T18:11:35.440

3

The simplest thing would be to scan your array, and store the indices of the n highest values. Increment the values of those elements.

This is going to be O(n) performance, and I don't think any fancier methods can beat that.

edit to add: you can sort the array in place in O(n) at best, in which case you can get the n highest values very quickly, but the requirement is to not change position of the elements, so you'd have to start with a copy of the array if you wanted to do that (or preserve ordering information so you could put everything back afterward).

edited May 13 '11 at 18:11

answered May 13 '11 at 17:28

Jeff Paulsen

2,132
1
12
10

1

Isn't it O(n + m), for an array of length m and n greatest elements? – YXD May 13 '11 at 17:33
@Mr E: You could use a MinHeap or something to get it a bit more efficient but yep it's dependent on both n and m. – Voo May 13 '11 at 17:57
Certainly, but by convention, when f(x) is a sum of multiple terms, the term with the largest growth rate is used. In this case I'm assuming that length will grow faster than than greatest-elements. – Jeff Paulsen May 13 '11 at 17:58
@Jeff Paulsen Sure if we can guarantee that M will stay small it's an easy solution that'll work well enough. The extra overhead of a minheap (and first either find a extra lib for it or implement it yourself) will surely be worse for small values. But for M=N which is possible, it'd turn into N^2 (and I think you can't do better than n log m here, sounds like the comparison sort boundary theorem should apply here as well) – Voo May 13 '11 at 18:06
@Jeff I don't know of any sorting algorithms that are faster that O(n) for arbitrary data. http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms – Chris Morgan May 13 '11 at 18:07
@Chris Morgan Well probably you could get away with a non-comparison sort here since we're talking about integers. So a radix/bucket sort should work. – Voo May 13 '11 at 18:11
Thanks guys - I changed it to say "O(n) at best". – Jeff Paulsen May 13 '11 at 18:12
@Voo Good point. I still like Jeff's original simple scanning answer the best. – Chris Morgan May 13 '11 at 18:18
If you denote n as thearray size then O(n) is achievable only if n=m, or I am mistaken? Can you comment on my implementation in the answer? If n>m you need to loop at each iteration over m to find the index to replace. – Marino Šimić May 13 '11 at 19:03

score 2 · Answer 2 · answered May 13 '11 at 17:27

2

You might be over engineering the solution to this problem: scan the array, from beginning to end, and mark the two largest elements. Return to the two greatest elements and add 1 to it. The solution shouldn't be longer than 10 lines.

answered May 13 '11 at 17:27

Kromagg

69
3

Oh. Yeah, that makes sense. ...dunno why I was complicating it like that, haha. – akbiggs May 13 '11 at 17:29
What if he wants the 10 greatest elements? are you going to keep 10 members for that? – RonK May 13 '11 at 17:30
if the number of elements to keep is less than log(n) then yes. Once it's log(n) then sorting might be better. – Lou Franco May 13 '11 at 17:32

score 1 · Answer 3 · answered May 13 '11 at 17:31

Loop over the array and keep track of the indices and values of the two largest items

a. Initialize the tracker with -1 for an index and MIN_INT for a value or the first two values of the array

b. At each step of the loop compare the current value against the two tracker values and update if necessary
Increment the two items

Any algorithm you choose should be O(n) for this. Sorting and n passes are way overkill.

score 0 · Answer 4 · edited May 23 '17 at 12:19

0

Find the nth largest element (call it K) using techniques here and here (can be done in linear time), then go through the array modifying all elements >= K.

edited May 23 '17 at 12:19

Community

1
1

answered May 13 '11 at 17:38

tarkeshwar

4,105
4
29
35

No it can't be done in linear time. Every algorithm on that side turns into at least n log n for K=N and I'm extremely sure that's an theoretical lower limit.. – Voo May 13 '11 at 18:01
http://en.wikipedia.org/wiki/Selection_algorithm says median-of-medians algorithm for selection is linear even in worst case. That makes the above solution linear. – tarkeshwar May 13 '11 at 19:28

score 0 · Answer 5 · answered May 13 '11 at 17:42

i would do something like this

int[] indices = new int[2];
int[] maximas = new int[] { 0, 0 };
int[] data = new int[] { 3, 4, 5, 1, 9 };
for (int i = 0; i < 5; ++i)
{
    if (data[i] > maximas[1])
    {
            maximas[0] = maximas[1];
            maximas[1] = data[i];
            indices[0] = indices[1];
            indices[1] = i;
    } 
    else if (data[i] > maximas[0])
    {
            maximas[0] = data[i];
            indices[0] = i;
    }
}

didn't test it, but I think it should work :)

Marino Šimić · Answer 6 · 2011-05-13T19:20:47.017

I have tought a bit about this but I cannot achieve more than worstcase:

O( n + (m-n) * n ) : (m > n)

best case:

O(m) : (m <= n)

where m = number of values, n = number of greatest value to search

This is the implementation in C#, but you can easily adapt to java:

        int n = 3;
        List<int> values = new List<int> {1,1,1,8,7,6,5};
        List<int> greatestIndexes = new List<int>();

        for (int i = 0; i < values.Count; i++) {
            if (greatestIndexes.Count < n)
            {
                greatestIndexes.Add(i);
            }
            else {
                int minIndex = -1, minValue = int.MaxValue;
                for (int j = 0; j < n; j++)
                {
                    if (values[greatestIndexes[j]] < values[i]) {

                        if (minValue > values[greatestIndexes[j]])
                        {
                            minValue = values[greatestIndexes[j]];
                            minIndex = j;
                        }
                    }
                }
                if (minIndex != -1)
                {
                    greatestIndexes.RemoveAt(minIndex);
                    greatestIndexes.Add(i);
                }
            }
        }

        foreach (var i in greatestIndexes) {
            Console.WriteLine(values[i]);
        }

Output:

8
7
6

Modifying the greatest elements of an array without changing their position?

6 Answers6