Find all pairs (x, y) in a sorted array so that x + y < z

Problem

Given a sorted integer array and number z find all pairs (x, y) in the array so that x + y < z. Can it be done better than O(n^2)?

Solution

Method 1

The solution can be found in O(n^2) where we select 1st element from n elements and 2nd element y from n-1 elements, and hence n(n-1)/2 ~ O(n^2)

Reference - stackoverflow

See also

• Asymptotic Notation
• Growth Rate - The Importance of Asymptotics
• For a Given node of a binary tree, print the K distance nodes.
• Find the distance between 2 nodes in Binary Tree
• Find the distance between 2 nodes in Binary Tree