167. Two Sum 2 - Input Array is Sorted - Medium

 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 0. There index1 = 1 and index2 = 2. We return [1,2]

Constraints:

  • 2 <= numbers.length <= 3 * 10**4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
Solution:
var twoSum = function(numbers, target) {
    const map = new Map();
    
    for (let i = 0; i < numbers.length; i++) {
        const component = target - numbers[i];

        if (map.has(component)) {
            return [map.get(component)+1, i+1];
            }
        
        map.set(numbers[i], i);
    }
}

Thoughts:
Happy with my solution. Figured it out on my own because I have tackled the easy two sum problem before and could remember the optimal solution for that as well. I needed to debug in vscode to clearly see the flow of the data so I could visually see what was happening. In an interview, I'm not sure I'd be able to see that flow and would struggle. For example, I couldn't initially work out what I should be storing in the map but seeing it in vscode made it clear. 7/10 understanding.

Comments

Post a Comment

Popular posts from this blog

28. Find the Index of the First Occurence in a String - Easy

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if the needle is not part of haystack. Example: Input: haystack = 'sadbutsad', needle = 'sad' Output: 0 Explanation: 'sad' occurs at index 0 and 6. The first occurrence is at index 0, so we return 0. Constraints: 1 <= haystack.length, needle.length <= 10**4 haystack and needle consist of only lowercase English characters. Solution: var strStr = function(haystack, needle) {          return haystack.indexOf(needle); } Thoughts: 10/10 easy.
Read more

121. Best Time to Buy and Sell Stock - Easy

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximise your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0 Example: Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. Constraints: 1 <= prices.length <= 10**5 0 <= prices[i] <= 10**4 Solution: var maxProfit = function(prices) {     let buyPrice = prices[0];     let profit = 0;     for (let i = 1; i < prices.length; i++) {          if (buyPrice > prices[i]) {               buyPrice = prices[i];         ...
Read more

58. Length of Last Word - Easy

Given a string s consisting of words and spaces, return the length of the last word in the string. A word is. a maximal substring consisting of non-space characters only. Example: Input: s = "Hello World" Output: 5 Explanation: The last word is "World" with length 5. Constraints: 1 <= s.length <= 10**4 s consists of only English letters and spaces ' '. There will be at least one word in s. Solution: var lenghtOfLastWord = function(s) {       return s.trim().split(' ').pop().length; } Thoughts: Super simple. 10/10 for confidence and understanding.
Read more