Problem

Given an array (or string), find the first element that does not repeat (i.e., appears exactly once). Return the element itself, or its index if required.

Examples

Example 1

1
2
3

Input: [2, 3, 4, 2, 3, 5, 4]
Output: 5
Explanation: 5 is the first element that does not repeat.

Example 2

1
2
3

Input: [1, 2, 2, 1, 3, 4, 3]
Output: 4
Explanation: 4 is the first unique element.

Example 3 (String)

1
2
3

Input: "abcdab"
Output: 'c'
Explanation: 'c' is the first non-repeating character.

Solution

Method 1 – Brute Force (Nested Loops)

Intuition

Check each element and see if it appears elsewhere in the array. The first element that does not repeat is the answer.

Approach

  1. For each element, check all other elements to see if it repeats.
  2. If not, return that element.
  3. If all elements repeat, return a special value (e.g., -1 or ‘’).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int firstUnique(std::vector<int>& arr) {
        for (int i = 0; i < arr.size(); ++i) {
            bool unique = true;
            for (int j = 0; j < arr.size(); ++j) {
                if (i != j && arr[i] == arr[j]) {
                    unique = false;
                    break;
                }
            }
            if (unique) return arr[i];
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int firstUnique(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean unique = true;
            for (int j = 0; j < arr.length; j++) {
                if (i != j && arr[i] == arr[j]) {
                    unique = false;
                    break;
                }
            }
            if (unique) return arr[i];
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def first_unique(self, arr: list[int]) -> int:
        for i in range(len(arr)):
            unique = True
            for j in range(len(arr)):
                if i != j and arr[i] == arr[j]:
                    unique = False
                    break
            if unique:
                return arr[i]
        return -1

Complexity

  • ⏰ Time complexity: O(n^2), since for each element we check all others.
  • 🧺 Space complexity: O(1), no extra space used.

Method 2 – Hash Map / Array Counting

Intuition

Count the frequency of each element using a hash map (or array for small ranges). The first element with count 1 is the answer.

Approach

  1. Traverse the array and count occurrences of each element.
  2. Traverse the array again and return the first element with count 1.
  3. If none, return a special value (e.g., -1 or ‘’).

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int firstUnique(std::vector<int>& arr) {
        std::unordered_map<int, int> freq;
        for (int x : arr) freq[x]++;
        for (int x : arr) if (freq[x] == 1) return x;
        return -1;
    }
};
1
2
3
4
5
6
7
8

class Solution {
    public int firstUnique(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
        for (int x : arr) if (freq.get(x) == 1) return x;
        return -1;
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def first_unique(self, arr: list[int]) -> int:
        freq = {}
        for x in arr:
            freq[x] = freq.get(x, 0) + 1
        for x in arr:
            if freq[x] == 1:
                return x
        return -1

Complexity

  • ⏰ Time complexity: O(n), two passes over the array.
  • 🧺 Space complexity: O(n), for the hash map.