Two Sum II – Input Array Is Sorted

Leetcode Problem: Two Sum II – Input Array Is Sorted

Objective:

Given a sorted array and target sum, find the two indexes that add up to the target sum.

Pattern: Two Pointer Technique

Approach:

Have one pointer at the start and one pointe…


This content originally appeared on DEV Community and was authored by Tammy Vo

Leetcode Problem: Two Sum II - Input Array Is Sorted

Objective:

Given a sorted array and target sum, find the two indexes that add up to the target sum.

Pattern: Two Pointer Technique

Approach:

  1. Have one pointer at the start and one pointer at the end of the array.
  2. Initialize the output int [] array with a size of 2, for the two indexes.
  3. Use a while loop with the condition where start < end, since the start index should never be greater than the end index. This means we have already checked all elements from left and right side.
  4. Inside while loop, check if the current sum is equal to the target. If it is, return the indexes.
  5. If the current sum is less than target, increment the start index.
  6. If the current sum is greater than target, decrement the end index.

Big-O Notation:

Time Complexity: O(n)
We have iterate through the while loop n times, for each element.

Space Complexity: O(1)
We do not use any additional data structures for storage.

Code:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // use two pointer techique because the input is sorted.
        int start = 0; 
        int end = numbers.length - 1;
        int [] result = new int [2];

        while (start < end){
            int sum = numbers[start] + numbers[end];

            if (sum == target){
                result[0] = start + 1;
                result[1] = end + 1;
                break;
            }

            if (sum < target){
                start++;
            } else {
                end--;
            }
        }
        return result;
    }
}


This content originally appeared on DEV Community and was authored by Tammy Vo


Print Share Comment Cite Upload Translate Updates
APA

Tammy Vo | Sciencx (2022-07-06T21:36:31+00:00) Two Sum II – Input Array Is Sorted. Retrieved from https://www.scien.cx/2022/07/06/two-sum-ii-input-array-is-sorted/

MLA
" » Two Sum II – Input Array Is Sorted." Tammy Vo | Sciencx - Wednesday July 6, 2022, https://www.scien.cx/2022/07/06/two-sum-ii-input-array-is-sorted/
HARVARD
Tammy Vo | Sciencx Wednesday July 6, 2022 » Two Sum II – Input Array Is Sorted., viewed ,<https://www.scien.cx/2022/07/06/two-sum-ii-input-array-is-sorted/>
VANCOUVER
Tammy Vo | Sciencx - » Two Sum II – Input Array Is Sorted. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2022/07/06/two-sum-ii-input-array-is-sorted/
CHICAGO
" » Two Sum II – Input Array Is Sorted." Tammy Vo | Sciencx - Accessed . https://www.scien.cx/2022/07/06/two-sum-ii-input-array-is-sorted/
IEEE
" » Two Sum II – Input Array Is Sorted." Tammy Vo | Sciencx [Online]. Available: https://www.scien.cx/2022/07/06/two-sum-ii-input-array-is-sorted/. [Accessed: ]
rf:citation
» Two Sum II – Input Array Is Sorted | Tammy Vo | Sciencx | https://www.scien.cx/2022/07/06/two-sum-ii-input-array-is-sorted/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts