Time Complexity for Array Max Duplicate

Question

Using only an array for a data structure, what would be the fastest time complexity in finding duplicate max values in the array?

I am thinking one loop is needed to find the max value and another loop would be needed to find if there are any duplicates. Each loop would have to touch each element once so it would be linear time complexity O(n). Given 2 loops we would have O(n) * O(n) = O(n^2).

Does this sound right or does anyone think it can all be done in one loop to keep the time complexity O(n).

I've looked the problem up, but I see fancy solutions like using a hash table. I need to use an array.

I agree that your solution is fine as-is. It could be "optimized" to use just one loop but that won't affect the complexity, and it is doubtful that it would make it much faster. (And the flip-side is that doing it in one loop makes the logic more complicated.) — Stephen C
– Stephen C, Commented Feb 9, 2023 at 1:20
Also ... those fancy solutions that use a hash table would almost certainly be slower for this problem. — Stephen C
– Stephen C, Commented Feb 9, 2023 at 1:23

Louis Wasserman · Accepted Answer · 2023-02-09 01:16:06Z

1

You already have a fine solution, you've just analyzed it incorrectly.

You do one loop to find the maximum value, and then you do another loop to find duplicates of the maximum value. That isn't a loop inside another loop, that's a loop after another loop -- and that's not O(n) * O(n), it's O(n) + O(n), which is just O(n) again.

No hash tables. No fancy data structures. You already have a good solution.

answered Feb 9, 2023 at 1:16

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Jax Over a year ago

Thanks for everyone's perspective. Okay so a loop inside of a loop, as long as every element is touched would be O(n^2), but 2 O(n) simplifies to O(n).

Jax Over a year ago

So, O(n) is good but do you think that is as good as we can do? I think it is because every element has to be touched once in a loop. So linear is the best it's gonna get using an an array.

Louis Wasserman Over a year ago

You have to visit every element, so yes, you can't do better than O(n).

Jax Over a year ago

I'm sorry I thought I had to get the count of max duplicates which would have been easy, but I really need to get the indices of the max duplicates. It seems like the time complexity should be the same, but I am unsure on the logic to accomplish that. Can't have variables to store index values because we would never know how many indices will have a max value.

Louis Wasserman Over a year ago

Well, in the worst case, you can do three loops: one to find the max value, one to count the duplicates, and one to fill an array that holds all the indices, since you'll know how big to make the array. (You can actually combine the loops to find the max value and to count the duplicates, but I won't spoil that part.)

|

Edd1e · Accepted Answer · 2023-02-09 01:14:47Z

Well, if you can't use hash table (which makes the problem o(n) time complexity and o(n) space complexity), i would use just sorting the array, and check with 2 pointers if any of the values is repeated. So after sorting the algorithm (O(nlogn)) i would make 2 variable i,j starting i at 0 and j at 1 and while j<arr.lenght, and check if there is duplicate between positions array[i] and arr[j]. Here is how i solved it in js:

function areThereDuplicates(...args){//Don't worry about this, imagine like it is an array
    args= typeof(args[0])=='string'?args.sort():args.sort((a,b)=>a-b)//I sorted the array
    let i=0
    let j=1
    while(j<args.length){
        let el= args[i]
        let secEl=args[j]
        if(el===secEl){
            return true
        }
        i++
        j++
    }
    return false
}

Collectives™ on Stack Overflow

Time Complexity for Array Max Duplicate

2 Answers 2

11 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

11 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related