Introduction

Counting unique values without rearranging an array is straightforward if you are allowed extra memory, and much more constrained if you are not. The first design decision is whether “do not rearrange” means “preserve the array exactly” or whether auxiliary storage is acceptable.

The Standard Solution Uses a Set

If the array must remain in its original order and you only need the count, a set is the simplest and most efficient solution. As you scan the array, insert each value into the set. Duplicate insertions do nothing, so the final size of the set is the number of distinct elements.

1def count_unique(values):
2    seen = set()
3    for value in values:
4        seen.add(value)
5    return len(seen)
6
7
8print(count_unique([4, 2, 4, 7, 2, 9, 9, 1]))

Output:

4

This runs in O(n) average time and uses O(u) extra space, where u is the number of unique values.

Why Preserving Order Does Not Change the Counting Logic

People often mention “without rearranging the array” because sorting is a common distinct-count technique. Sorting groups equal values together, but it mutates the array or requires a sorted copy. If mutation is not allowed, a set avoids the problem entirely because it never changes the input sequence.

1numbers = [4, 2, 4, 7, 2, 9, 9, 1]
2unique_total = count_unique(numbers)
3print(numbers)
4print(unique_total)

The array stays exactly as it started.

If You Need the Unique Values in First-Seen Order

Sometimes the real need is not only the count, but also the sequence of first appearances. You can collect both with one pass.

1def unique_values_in_order(values):
2    seen = set()
3    ordered = []
4
5    for value in values:
6        if value not in seen:
7            seen.add(value)
8            ordered.append(value)
9
10    return ordered
11
12
13print(unique_values_in_order([4, 2, 4, 7, 2, 9, 9, 1]))

Output:

[4, 2, 7, 9, 1]

Then len(ordered) is your unique count.

What If Extra Space Is Restricted

If you are not allowed to rearrange the array and also not allowed significant extra storage, the problem gets harder. Without storing what you have seen, the only exact alternative is repeated scanning.

1def count_unique_no_extra_space(values):
2    unique_count = 0
3
4    for i in range(len(values)):
5        found_earlier = False
6        for j in range(i):
7            if values[j] == values[i]:
8                found_earlier = True
9                break
10        if not found_earlier:
11            unique_count += 1
12
13    return unique_count
14
15
16print(count_unique_no_extra_space([4, 2, 4, 7, 2, 9, 9, 1]))

This uses constant extra space, but it takes O(n^2) time. That is the usual tradeoff when you forbid both mutation and storage.

Small Numeric Ranges Allow a Better Space Tradeoff

If the values are integers from a known small range, a boolean array or count array can be cheaper than a hash set.

1def count_unique_small_range(values, max_value):
2    seen = [False] * (max_value + 1)
3    total = 0
4
5    for value in values:
6        if not seen[value]:
7            seen[value] = True
8            total += 1
9
10    return total

That is still auxiliary space, but it is predictable and often faster than hashing.

Choose the Constraint That Actually Matters

In real code, the set-based solution is usually correct because it is simple, fast, and does not alter the array. If the requirement is “do not rearrange the elements,” that does not automatically mean “use no extra memory.” Those are different constraints and should not be mixed together.

Common Pitfalls

• Assuming that preserving the array means a set is forbidden when the requirement only bans rearrangement.
• Sorting the array in place and accidentally violating the “do not rearrange” rule.
• Using a constant-space nested-loop solution when a set would be simpler and much faster.
• Forgetting that counting unique values and finding non-repeating values are different problems.
• Choosing a fixed-size marker array without confirming the numeric range is small enough.

Summary

• A set gives the cleanest exact solution when the array must stay in its original order.
• The set approach runs in O(n) average time and leaves the input untouched.
• Constant extra space is possible only with slower repeated scanning unless other assumptions hold.
• A small known numeric range can justify a boolean or count array.
• Clarify whether the real constraint is “no rearrangement,” “low memory,” or both.