arcbjorn

thoughtbook

Friday, February 24, 2023

Two sum

Leetcode 1 problem.

Go

Array iteration

  • Time complexity: O(n)O(n) - n is a length of an array of integers
  • Auxiliary space: O(n)O(n) - constant amount of space
func twoSum(nums []int, target int) []int {
    // key is number, value is it's index
    numberIndexMap := make(map[int]int)
    
    for index, num := range nums {
        // find first number that equals to the difference between current number and target number
        if value, isFound := numberIndexMap[target - num]; isFound {
            // return found number and current number indices
            return []int{ value, index }
        } 
        
        numberIndexMap[num] = index
    }
    
    return nil
}
  • Time complexity: O(log(n))O(log(n)) - n is a length of an array of integers
  • Auxiliary space: O(1)O(1) - constant amount of space
func arrangeCoins(n int) int {
    low := 0
    mid := 0
    high := int(math.Sqrt(float64(n))) * 2

    for low < high {
        mid = low + (high - low) / 2

        currentCoinNumber, nextCoinNumber := getMaxCoinNumber(mid), getMaxCoinNumber(mid+1)

        if currentCoinNumber <= n && n < nextCoinNumber { 
            return mid 
        } else if n < currentCoinNumber { 
            high = mid - 1 
        } else if n >= nextCoinNumber { 
            low = mid + 1
        }
    }

    return low
}

func getMaxCoinNumber(n int) int {
    return int((n + 1) * n / 2)
}

Typescript

  • Time complexity: O(n)O(n) - n is a length of an array of integers
  • Auxiliary space: O(n)O(n) - constant amount of space
function twoSum(nums: number[], target: number): number[] {
    // key is number, value is it's index
    const numberIndexMap = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        // difference between current number and target number
        const difference = target - nums[i];
        
        if (numberIndexMap.has(difference)) {
            return [numberIndexMap.get(difference), i];
        }
        
        numberIndexMap.set(nums[i], i);
    }
    
    return [];
}
Creative Commons Licence