# Count the distinct absolute values in the sorted array

Given an array of sorted integers which may have several duplicates elements, count the number of distinct absolute values in the array.

For example,

Input: { -1, -1, 0, 1, 1, 1 }
Output: The number of distinct absolute values are 2 (0 and 1)

Input: { -2, -1, 0, 1, 2, 3 }
Output: The number of distinct absolute values are 4 (0, 1, 2 and 3)

Input: { -1, -1, -1, -1 }
Output: The number of distinct absolute values are 1 (only 1)

We can easily solve this problem by inserting the absolute value of each array element into a set. We know that a Set doesn’t permit duplicates and hence its size would be the desired count.

## C++

Output:

The number of distinct absolute values are 2

## Java

Output:

The number of distinct absolute values are 2

Above approach doesn’t take advantage of the fact that the input is already sorted and also takes O(n) extra space. We can use Sliding Window approach to easily solve this problem in O(1) extra space.

The idea is to initialize the distinct count as number of elements present in the input. The program checks for a pair with 0-sum with the help of two index variables (initially pointing to two corners of the array). If the pair with 0-sum is found (or duplicates are encountered), we decrement the count of distinct elements. Finally, the updated count is returned.

## C++

Output:

The number of distinct absolute values are 2

## Java

Output:

The number of distinct absolute values are 2

(1 votes, average: 5.00 out of 5)