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++

Download   Run Code

Output:

The number of distinct absolute values are 2

Java

Download   Run Code

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++

Download   Run Code

Output:

The number of distinct absolute values are 2

Java

Download   Run Code

Output:

The number of distinct absolute values are 2

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of