absDistinct.md

Description: Given a sorted array of integers, count the number of distinct absolute values in the array.

Examples

Example 1:

Input: numbers = [-5, -3, -1, 0, 3, 6] Output: 5

Example 2:

Input: numbers = [-2, -1, 0, 1, 2, 2] Output: 3

Example 3:

Input: numbers = [-1, -1, -1, 1, 1, 1] Output: 1

Example 4:

Input: numbers = [] Output: 0

Algorithmic Steps This problem is solved using a two-pointer approach and a set:

1. Sort the array in non-decreasing order (if not already sorted).
2. Initialize two pointers, left at the start and right at the end of the array.
3. While left <= right:
   • Compare the absolute values at left and right.
   • Add the larger absolute value to a set.
   • Move the pointer corresponding to the larger absolute value.
4. Return the size of the set.

Time and Space complexity:

• Time complexity: O(n), where n is the number of elements in the array (if already sorted; otherwise, O(n log n) for sorting).
• Space complexity: O(n) in the worst case (for the set).