Arrays

Question 1

Search in rotated sorted array

Answer 1

1. Binary search, compare start with mid to find ascending or descending
2. Then check whether the target falls into the range

Question 2

Duplicate element in 0 - n -1 array

Answer 2

1. Use tortoise and hare algo
2. Find the cycle using do while and equality
3. Set tortoise to start and iterate both by 1 and find the intersection
   Hashset and this algo are same time complexity, but this requires O(1) space complexity

Question 3

Sliding window maximum

Answer 3

1. Use queue to maintain the order of insertion (of indexes)
2. Remove the out of index by i - k + 1 with peek value
3. Remove the indexes with lower value than the current index