CODEWITHSUNDEEP
algorithm
shilk
shilk

Reputation: 589

Finding the minimum unique number in an array

The minimum unique number in an array is defined as min{v|v occurs only once in the array} For example, the minimum unique number of {1, 4, 1, 2, 3} is 2. Is there any way better than sorting?

Upvotes: 5

Views: 2551

Answers (3)

Upender Reddy
Upender Reddy

Reputation: 1

Python version using dictionary.
Time complexity O(n) and space complexity O(n):

from collections import defaultdict
d=defaultdict(int)
for _ in range(int(input())):
    ele=int(input())
    d[ele]+=1
m=9999999
for i in d:
    if d[i]==1 and i<m:
        m=i
print(m if m!= 9999999 else -1)

Please tell me if there is a better approach.

Upvotes: 0

PermanentGuest
PermanentGuest

Reputation: 5331

You don't need to do full sorting. Perform bubble sort inner loop until you get distinct minimum value at one end. In the best case this will have time complexity O(k * n) where k = number of non-distinct minimum values. However worst case complexity is O(n*n). So, this can be efficient when expected value of k << n.

I think this would be the minimum possible time complexity unless you can adapt any O(n * logn) sorting algorithms to the above task.

Upvotes: 0

walrii
walrii

Reputation: 3522

I believe this is an O(N) solution in both time and space:

HashSet seenOnce;     // sufficiently large that access is O(1)
HashSet seenMultiple; // sufficiently large that access is O(1)

for each in input // O(N)
    if item in seenMultiple
        next
    if item in seenOnce
        remove item from seenOnce
        add to item seenMultiple
    else
        add to item seeOnce

smallest = SENTINEL
for each in seenOnce // worst case, O(N)
    if item < smallest
        smallest = item

If you have a limited range of integral values, you can replace the HashSets with BitArrays indexed by the value.

Upvotes: 5

Related Questions