arcbjorn

# thoughtbook

Friday, February 24, 2023

# Two sum

Leetcode 1 problem.

## Go

#### Array iteration

• Time complexity: $O(n)$ - n is a length of an array of integers
• Auxiliary space: $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))$ - n is a length of an array of integers
• Auxiliary space: $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)$ - n is a length of an array of integers
• Auxiliary space: $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 [];
}