Medium

• Shubham Kumar
• 23 Jul, 2026
• • Code

[Neetcode] Two Integer Sum II

Basically you have a sorted array of integers and you need to find the index i, j which will sum up to a target. Approach 1 - Bruteforce The simplest solution is loop through all the integers combinations and find the indices. This is basically looping twice each number -> O(n^2), not very good.We can make the above one more optimal by starting the second loop after the current index. This will reduce our iterations by half, making it n(n-1)/2. This is also O(n^2).We can add one more optimization by pruning as soon as second loop sums to a number greater than target. As the array is sorted, any number after the number which resulted in sum greater than target will also result in a sum greater than the target. Worst case this will also be O(n^2).But we got a clue here, the clue is traversing in reverse order if we get a sum less than target then we no longer need to search a number before the index. Basically, if sum of 1st and last is less than the target, then good guess would be check the 2nd number and last number. And if 1st and lat is greater than the target, then a good guess would be check 1st and 2nd last. And so on. Approach 2 - 2 pointers Take 2 pointers, l at the start of the array and r at the last of the array. If the sum of numbers at the pointers is greater than target then check r-1 and if it is less than the target then check l+1. This will give us a solution which is O(n) as none of the numbers are being passed more than once.