โ† Visa questions

Pairs with product less than or equal to a value in O(n)

Filed under Visa

Free read 2 of 3

Use 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

  1. Use two pointers, left and right, to evaluate products.

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.