Count unique values in a sorted array

Easy

≈ 8 minute session

Back to curriculum Next lesson

Summary

Count distinct values in a sorted array using a two-pointer in-place approach.

Problem statement

Given a sorted list of integers (non-decreasing), return the count of unique values present. Implement an in-place two-pointer technique where one pointer tracks the position to write the next unique value and the other scans the array. You should return the number of unique values (an integer).

Task

Return the number of unique values in a sorted array in O(n) time and O(1) extra space.

Examples

Duplicates collapsed

Input

arr = [1, 1, 2, 2, 3]

Output

Explanation

There are three unique values: 1, 2, and 3.

Input format

A sorted list of integers 'arr'. Function signature: count_unique(arr).

Output format

Return an integer: the number of unique values in arr.

Constraints

0 <= len(arr) <= 10^5. Aim for O(n) time and O(1) extra space.

Samples

Sample input 0

[1, 2, 3, 4]

Sample output 0

Explanation 0

All values are unique.

Code editor

Loading editor…

AI assistant

Ask me anything!

Need help? I can explain the core idea behind this problem, review your current code, and give targeted hints. Use “Teach Theory” for the concept, “Get AI hint” for a quick scaffold nudge, or ask a specific question below.

Chat history is temporary and will not be saved.

03:43 PM

Free preview includes 1 Teach Theory response and 1 AI hint on each of the first 3 lessons in this module.