posted 7 months ago

Hi everyone,

I came across below problem and here's my take on it. Can we discuss the solution?

Time Complexity of

No. of elements in the array is N and no. of elements to be returned is K.

- Assume that (Arrays.sort(a);) uses Merge/quick sort, O(N logN)

- for loop, O(K)

- result[j] = a[i];

-- a[i],access of array is constant, O(1)

-- result[j], insertion in array, O(K)

O(N logN) + O(K) + O(1) + O(K)

= O(N logN + 2K)

= O(N logN + K) (Drop the constant)

= O(N logN) (for very small values of K)

Does this sound right? Thank you

I came across below problem and here's my take on it. Can we discuss the solution?

**Problem statement**(AS IS): Write a java program to find out the first three highest numbers of the integer array in descending order. Explain the time complexity of your solution (Big O Notation)Time Complexity of

`getArray`method:No. of elements in the array is N and no. of elements to be returned is K.

- Assume that (Arrays.sort(a);) uses Merge/quick sort, O(N logN)

- for loop, O(K)

- result[j] = a[i];

-- a[i],access of array is constant, O(1)

-- result[j], insertion in array, O(K)

O(N logN) + O(K) + O(1) + O(K)

= O(N logN + 2K)

= O(N logN + K) (Drop the constant)

= O(N logN) (for very small values of K)

Does this sound right? Thank you

posted 7 months ago

So you are passing a sorted 3‑element array to a method to sort it and find its first 3 elements? Yes, that would run in

*n*log*n*complexity, but have you considered other approaches? Have you tried it with a larger array Let's try this array:-I can envisage a solution which has some clunky features but (depending on your wanting three solutions) will run in linear complexity.
Saurabh Pillai

Ranch Hand

Posts: 541

posted 7 months ago

Hi Campbell,

If you look at the commented code, I have tried to pass 3 different size arrays (edge cases) to test if it fails. Irrespective of size of the array and order of elements, my proposed solution will first sort the array and retrieve last 3 elements.

You are suggesting that you have a solution which will run in linear complexity. Is it one of the sorting algorithms and instead of sorting whole array, you only care about sorting until you get 3 max numbers?

If you look at the commented code, I have tried to pass 3 different size arrays (edge cases) to test if it fails. Irrespective of size of the array and order of elements, my proposed solution will first sort the array and retrieve last 3 elements.

You are suggesting that you have a solution which will run in linear complexity. Is it one of the sorting algorithms and instead of sorting whole array, you only care about sorting until you get 3 max numbers?

posted 7 months ago

How about using variables to store the highest elements? Would that let you do it in one pass?

[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

posted 7 months ago

If you had a variable "max1", how would you go through the non-sorted list of numbers once so that max1 ends up with the highest value in the list? (This is pretty straight forward but might give you a clue as to how to do the next step.)

Now, if you add a variable "max2" that would have the next highest number, how would you go through the non-sorted list only once and end up with max1 and max2 containing the highest and 2nd highest values in the list? (This should give you the pattern for how to find the N highest numbers if you wish.)

max3?

Now, if you add a variable "max2" that would have the next highest number, how would you go through the non-sorted list only once and end up with max1 and max2 containing the highest and 2nd highest values in the list? (This should give you the pattern for how to find the N highest numbers if you wish.)

max3?

The most difficult part of wild life photography is getting them to sign the model release.

posted 7 months ago

- 1

Hmm... first of all: the question is about giving

Some questions about the suggested O(N) solution: how would you prevent that max1 is getting selected in every step? Removing max1 from the array is a possibility, but what is the time complexity of that? Or switching max1 to the end? That would require giving the length of the array to be interrogated. What if K is, say, N - 3? Would you still apply this method?

Sorting the array (possibly with a suitable comparator) and getting the first K numbers is a fine general solution.

**a**solution and the time complexity of that. It is not asked to give an optimal solution.Some questions about the suggested O(N) solution: how would you prevent that max1 is getting selected in every step? Removing max1 from the array is a possibility, but what is the time complexity of that? Or switching max1 to the end? That would require giving the length of the array to be interrogated. What if K is, say, N - 3? Would you still apply this method?

Sorting the array (possibly with a suitable comparator) and getting the first K numbers is a fine general solution.

posted 6 months ago

- 1

The sentence on line 20, Arrays.sort(a);, is very expensive. As the entry array becomes larger, the program slows down.

Imagine you want the tallest man in a country. What would you do?

1. you order them all in one row from the largest to the smallest and then take the tallest, or

2. you just put them all in one row and go through the row always keeping the highest you find

The first aproach is your solution. It is a simple line of code, Arrays.sort(a);, but it is very expensive for the computer.

If the array has millions of items, you don't need or want to sort them all just to get the 3 biggest ones. That's very expensive. It is best aproach to explore the entire array in one pass and take the 3 biggest elements. First try to do it only with the largest element. When you do, then you mess with the 3 biggest elements.

Imagine you want the tallest man in a country. What would you do?

1. you order them all in one row from the largest to the smallest and then take the tallest, or

2. you just put them all in one row and go through the row always keeping the highest you find

The first aproach is your solution. It is a simple line of code, Arrays.sort(a);, but it is very expensive for the computer.

If the array has millions of items, you don't need or want to sort them all just to get the 3 biggest ones. That's very expensive. It is best aproach to explore the entire array in one pass and take the 3 biggest elements. First try to do it only with the largest element. When you do, then you mess with the 3 biggest elements.

Campbell Ritchie

Marshal

Posts: 58454

178

Piet Souris

Rancher

Posts: 2460

80

posted 3 months ago

The adage on CodeRanch is always that performance is only an issue when it is an issue. But not in this case, apparently.

If the assignment was to find the N largest elements, with N being a parameter, then what would be the time complexity of this solution? (think of insertion sort).

If the assignment was to find the N largest elements, with N being a parameter, then what would be the time complexity of this solution? (think of insertion sort).

It is sorta covered in the JavaRanch Style Guide. |