CODEWITHSUNDEEP
arraysalgorithmsortingdistinct-values
qwerty
qwerty

Reputation: 361

Alternative O(N^2) time complexity with O(1) space complexity for finding distinct values in array

I am trying to see whether there is any alternative to brute force algorithm (or a slight improvement/worst performance to a naive brute force algorithm) that will still result in O(N^2) time complexity and O(1) auxiliary space.

This is my brute force pseudocode:

    procedure distinct(Input: array)                             
        for i=0 to i < length of array                      
            for j=i+1 to j < length of array                 
               if array[i] == array[j] and i != j then  
                  return false                        
               end if
               increment k
            end for
            increment j
        end for
        return true
    end procedure

I know that brute force algorithm is a terrible solution and there are many ways of achieving much better performance (using data sets or achieving O(N) time complexity and O(1) space complexity), however out of pure interest I am trying to find the O(N^2) worst case time complexity and O(1) space complexity. Is it even possible?

I was thinking that I could possibly apply a sorting algorithm (e.g. Bubble or Insertion sort), then use a for loop to go through sorted array, but would that still give me a quadratic function and not O(N^3)?

Upvotes: 1

Views: 725

Answers (1)

Tamas Ionut
Tamas Ionut

Reputation: 4410

Sort the array using heapsort and stop whenever you find two equal elements:

  • O(NLogN) time complexity
  • O(1) space complexity

You can also look for other (more advanced algorithms) for this purpose here

Selection and Insertion sort are 2 alternatives with:

  • O(NxN) time complexity
  • O(1) space complexity

Upvotes: 2

Related Questions