Pairs with product less than or equal to a value in O(n)
Filed under Visa
Free read 2 of 3Use two pointers, left and right, to evaluate products.
The question
Given a sorted array and a target value, find the number of pairs (i, j) such that arr[i] * arr[j] <= target.
Constraints
- Array is sorted.
- Time complexity must be O(N).
- Handle negative numbers if applicable.
Examples
- Input
- arr = [1, 2, 3, 4], target = 5
- Output
- 4
- Why
- Pairs: (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (3,1), (4,1). Wait, distinct pairs: (1,1), (1,2), (1,3), (1,4), (2,1), (2,2).
Approach
Use two pointers, left and right, to evaluate products.
Since the array is sorted, if arr[left] * arr[right] <= target, then all elements between left and right also satisfy the condition.
Add the count of valid pairs and adjust pointers accordingly.
Tips
- What they are testing: Test with negative numbers which change the product logic.
- Common mistake: Assuming the product is always increasing, which fails if the array contains negative numbers.
Related Visa questions
Collected from public candidate posts and coding forums. Updated Nov 2026.