Algos

Question 1

Given an integer, convert it to a Roman numeral

Answer 1

class Solution:
def intToRoman(self, num: int) -> str:
# Creating Dictionary for Lookup
num_map = {
1: “I”,
5: “V”, 4: “IV”,
10: “X”, 9: “IX”,
50: “L”, 40: “XL”,
100: “C”, 90: “XC”,
500: “D”, 400: “CD”,
1000: “M”, 900: “CM”,
}

    # Result Variable
    r = ''
    
    
    for n in [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]:
        # If n in list then add the roman value to result variable
        while n <= num:
            r += num_map[n]
            num-=n
    return r

Question 2

2sum (unordered): Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Answer 2

func twoSum(nums []int, target int) []int {
// Space: O(n)
s := make(map[int]int)

// Time: O(n)
for idx, num := range nums {
    // Time: O(1)
    if pos, ok := s[target-num]; ok {
        return []int{pos, idx}
    }
    s[num] = idx
}
return []int{} }

Question 3

2sum (ordered): Given a sorted array of unique integers and a target integer, return true if there exists a pair of numbers that sum to target, false otherwise. This problem is similar to Two Sum.

Strategy: 2 pointers

Answer 3

func checkForTarget(nums []int, target int) bool {
left := 0
right := len(nums) - 1

for left < right {
	curr := nums[left] + nums[right]
	if curr == target {
		return true
	}
	if curr > target {
		right -= 1
	} else {
		left += 1
	}
}

return false }

Question 4

Best time to buy and sell stock:

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize 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

Strategy: two pointers

Answer 4

class Solution:
def maxProfit(self, prices):
buy = prices[0]
profit = 0
for i in range(1, len(prices)):
if prices[i] < buy:
buy = prices[i]
elif prices[i] - buy > profit:
profit = prices[i] - buy
return profit

Question 5

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Answer 5

func productExceptSelf(ary []int) []int {
ans := make([]int, len(ary))
ans[0] = 1

fmt.Println("Filling ans slice with the running product of ary except for the last number in ary")

for i := 1; i < len(ary); i++ {
	ans[i] = ans[i-1] * ary[i-1]
}
right := 1
for i := len(ary) - 1; i >= 0; i-- {
	ans[i] *= right
	right *= ary[i]
}
return ans }

Question 6

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Strategy: Sliding window

Answer 6

func maxSubArray(nums []int) int {
cur := nums[0]
ans := nums[0]

// Iterate through each element starting from the second one
for i := 1; i < len(nums); i++ {
    // Update cur to be the maximum of either nums[i]+cur or nums[i]
    cur = max(nums[i]+cur, nums[i])
    // Update ans to be the maximum of ans and cur
    ans = max(ans, cur)
}

return ans  // Return the maximum sum subarray }

Question 7

Given an integer array nums, find a
subarray that has the largest product, and return the product.

Strategy: Sliding window

Answer 7

func maxProduct(nums []int) int {
n := len(nums)
curMax, curMin := 1, 1

res := math.MinInt
for i := 0; i < n; i++ {
	tmp := curMax * nums[i]
	curMax = max(nums[i], nums[i]*curMin, tmp)
	curMin = min(nums[i], nums[i]*curMin, tmp)
	res = max(res, curMax)
}
return res }

Question 8

Find Minimum in Rotated Sorted Array:

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Answer 8

func findMin(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := (left + right) / 2
		if nums[mid] > nums[right] {
			left = mid + 1
		} else {
			right = mid
		}
	}

	return nums[left]
}

Question 9

Search in Rotated Sorted Array:
There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Solution referece: https://leetcode.com/problems/search-in-rotated-sorted-array/solutions/3879263/100-binary-search-easy-video-o-log-n-optimal-solution/

Answer 9

func search(nums []int, target int) int {
   l, r := 0, len(nums) -1

	for l <= r {
		m := (r + l) / 2

        if nums[m] == target {
            return m
        }

		if nums[l] <= nums[m] {
			if nums[l] <= target && target < nums[m] {
				r = m - 1
			} else {
				l = m + 1
			}
		} else {
			if nums[m] < target && target <= nums[r] {
				l = m + 1
			} else {
				r = m - 1
			}
		}
	}

	return -1
}