Finding unique numbers in a sorted array is a common problem that often surfaces in algorithm design and interview questions. In general, removing duplicates from arrays requires at least linear time, specifically $O(n)$. However, a sorted array allows us to use its properties to optimize the operation. This article delves into the methodology and concepts for retrieving unique elements from a sorted array in less than $O(n)$ time complexity.

The Problem

Given a sorted array, the task is to find all the distinct numbers. For example, if the input array is [1, 1, 2, 2, 3, 4, 4, 5], the output should be [1, 2, 3, 4, 5].

Techniques for Finding Unique Numbers

A naive approach to solving this problem is to scan the array from beginning to end, adding only those elements that haven't appeared before to a new list. However, this takes $O(n)$ time. To achieve less than $O(n)$, we need a more strategic approach.

Using Two Pointers

For a sorted array, a two-pointers technique can be most effective:

1. Initialize Two Indexes:
   • Set the first pointer i to point at the first element.
   • Set the second pointer j to point at the second element.
2. Traverse the List:
   • Increment j and compare the elements at pointers i and j.
   • If the elements are equal, simply move j ahead to skip the duplicate.
   • If they are different, this means that the element at j is a new unique element, and i should be moved to j.
3. Copy Unique Elements:
   • After the completion of the loop, elements from the start to i represent the list of unique elements.

Python Implementation

Here is a concise Python implementation using the two-pointer technique:

1def find_unique_elements(sorted_array):
2    if not sorted_array:
3        return []
4
5    i = 0
6    for j in range(1, len(sorted_array)):
7        if sorted_array[j] != sorted_array[i]:
8            i += 1
9            sorted_array[i] = sorted_array[j]
10
11    return sorted_array[:i+1]
12
13# Example Usage
14result = find_unique_elements([1, 1, 2, 2, 3, 4, 4, 5])
15print(result)  # Output: [1, 2, 3, 4, 5]

Why Less Than O(n) Complexity is Impractical

While the two-pointer method is optimal for a sorted array, the claim of achieving a complexity of less than $O(n)$ is a challenging endeavor due to the following reasons:

• Data Dependency: The complexity often depends on data-driven factors. For random data or specific patterns, operations might appear faster, but the worst-case scenario will inherently remain at $O(n)$.
• Access Patterns: In standard computational models, each element must be examined at least once to determine its uniqueness, which cannot logically be performed in less than $O(n)$.
• Information Theory and Limits: The lower bounds on complexity for most search and sort operations on arbitrary input datasets are constrained by information theory, which states that each element comparison provides information that contributes to problem-solving.

Optimizations in Practice

While reducing complexity below $O(n)$ is theoretically untenable in this context, we can adopt a different perspective and practice optimizations such as:

1. Memory vs. Time Trade-off:
   Use of additional data structures like hash tables in cases where the array isn't necessarily ordered but needs quick lookups.
2. Application of Specialized Hardware:
   Leverage vectorized operations or specialized architectures to perform computations more rapidly in practical applications.
3. Batch Processing:
   Divide tasks into smaller chunks processed concurrently in a parallel computing environment.

Summary Table

Conclusion

In summary, finding unique elements in a sorted array efficiently leverages the array's ordering to achieve an optimal time complexity of $O(n)$ via a two-pointer method. While achieving less than $O(n)$ remains technically impractical, understanding the constraints and potential optimizations can guide us toward more efficient implementations in broader applications.