I am trying to solve the Two Sum II - Input Array Is Sorted question on leetcode, it's giving me Time Limit Exceeded so I guess my code isn't optimized well and needs more efficient solutions. But I am not so good at it so to be specific how can I remove two for-loops with one in my code.
Ques1: Two Sum II - Input Array Is Sorted
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Your solution must use only constant extra space.
Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Ques link
My code: Test cases 20 / 21
var twoSum = function(numbers, target) {
let arr=[];
for(let i=0; i<numbers.length; i++){
let findNum= target - numbers[i];
for(let j=i+1;j<numbers.length; j++){
if(numbers[j]===findNum)
arr.push(i+1, j+1);
}
}
return arr
};
How can I optimize my code so that it can run all test cases?
You can use the two-pointer approach,
I will not post the actual answer because that would spoil the fun.
I have an answer for Question 2. You have nested for loops. The nested loop will run for n - i times each time, where i varies from 1 to n. So the total time complexity of the code would be (n-1) + (n-2) + ... + 0, which would be (n*(n-1))/2. This is order O(n^2) solution. In the question n is 3 * 10^4 which would result in more than 10^8 operations a second. So it will give Time Limit Exceeded error. Now to solve this, you can use the property of sorted array. We can take two pointers, one at the beginning of the array and one at the last index. There would be three cases:
We will do it till i is not equal to j. Here is the full code.
var twoSum = function(numbers, target) {
enter code here
let ans = [];
while(i<j) {
if(numbers[i] + numbers[j] > target) {
j--;
}
else if(numbers[i] + numbers[j] < target) {
i++;
}
else {
ans.push(i+1);
ans.push(j+1);
break;
}
}
return ans;
};