Leetcode 5

Question 1

Merge Sorted Arrays

Answer 1

In place relies on three pointers

Time: O(n), Space: O(1)

Question 2

Decode String

Answer 2

Use two stacks, one for number and one for string.

Time: O(maxK*n), K is max value of k and n is length of the string. We traverse a string of size n and iterate k times to decode each pattern of form k[string]

Space: O(m+n), where m is the number of letters(a-z) and n is the number of digits(0-9). Worst case, stringStack = m, countStack = n.

Question 3

Pow(x, n)

Answer 3

Brute force is just multiply x for n times. time O(n), space O(1)

However, if we have x^n, x^(2n) is just x^n * x^n. Recursion -> Time: O(logn), space O(logn) b/c for each computation we need to store the result of x^n/2

Question 4

Validate Palindrome

Answer 4

Two points starting at beginning and end, check if both are lower case, if so then check if they’re the same. If not, return false

Time: O(n), Space: O(1)

Question 5

First Bad Version

Answer 5

Use binary search. If isBadVersion(mid) = false, we know all versions preceding and including mid are all good.

Time: O(logn), Space: O(1)