LeetCode's Array/String
Two sum I, II, Valid palindrome, Implement strstr(), Reverse words in string, Longest substring without repeating characters, Missing ranges, One edit distance
1. Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
- Input: nums = []int{2, 5, 4}, target = 6
Output: [0, 2] since nums[0] + nums[2] = 2 + 4 = 6
Approach:
- Use a hash map to store the value and its index as we iterate through the
list.
- Within each iteration, look up the difference of target and the current
value to see if we have seen that number.
- Simply return two cached indices once that condition meets.
Cost:
- O(n) time, O(n) space.
2. Given a sorted array of integers, return indices of the two numbers such that they add up to a specific target.
Example:
- Input: nums = []int{2, 3, 4}, target = 6
Output: [0, 2] since nums[0] + nums[2] = 2 + 4 = 6
Approach:
- Since the array is sorted, can use two-pointer approach that has one point
to the start of the list while the other point at the end and move the
toward each other.
Cost:
- O(n) time and O(1) space.
3. Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Example:
- Input: "A man, a plan, a canal: Panama"
Output: true
- Input: "race a car"
Output: false
Approach:
- Use two pointers approach that have one point to the start of the string and
the other point at the end.
- Move them toward each other and compare if they're the same characters while
skipping non-alphanumeric characters and ignoring cases.
Cost:
- O(n) time, O(1) space.
4. Implement strstr() that finds the first occurrence of the substring needle in the string haystack. It returns -1 if needle is not part of the haystack.
Example:
- Input: haystack = "aaabacd", needle = "ba"
Output: 3, because needle "ba" starts at index 3 in the haystack.
Approach:
- Scan the needle with the haystack from its first position and start matching
all subsequent letters one by one.
- If one letter does not match, start again with the next position in the
haystack.
Cost:
- O(nm) time, O(1) space, where n is the length of haystack while m is the
length of needle.
5. Given a string, reverse it word by word.
Example:
- Input: "hard so be to have not does interview coding"
Output: "coding interview does not have to be so hard"
Approach:
- Approach with a two-pass solution.
- The first pass is to split the string into an array of words separated by
spaces.
- The second pass is to reverse the order of words in the array by using
two-pointer approach: swap two values on both ends as we move toward the
middle.
- Concatenate the values of ordered array to create a final string.
Cost:
- O(n) time, O(n) space.
6. Given a string, find the length of the longest substring without repeating characters.
Example:
- Input: "abcabcbb"
Output: 3
Explanation: The longest substring is "abc" with the length of 3.
- Input: "bbbbb"
Output: 1
Explanation: The longest substring is "b" with the length of 1.
Approach:
- Iterate through the string and keep track of the maximum length of non-repeating
characters using a hashmap that maps characters to their indices.
- Could skip characters immediately if we found a repeating character.
Cost:
- O(n) time, O(m) cost where m < n and n is the length of the string.
7. Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.
Example:
- Input: []int{0, 1, 6, 16, 66, 99}
Output: []string{"2-5", "7-15", "17-65", "67-98"}
- Input: []int{6, 16, 66}
Output: []string{"0-5", "7-15", "17-65", "67-99"}
Approach:
- Keep two pointers where one is ahead of the other by 1 index.
- Iterate through the list, calculate the difference of two consecutive numbers
in the list at each step and append it to a new list.
Cost:
- O(n) time, O(m) space, where m < n and n is the size of the input.
8. Given two strings, determine if they are both one edit distance apart.
Example:
- Input: "abcde", "abXde"
Output: true
Explanation: Only "c" in S is replaced by "X" in T.
- Input: "abcde", "abcXde"
Output: true
Explanation: "X" is inserted between "c" and "d" in S to get T.
Approach:
- Use two-pointer approach to traverse both strings at the same time and
keep track of count of difference characters.
Cost:
- O(n) time, O(1) space
For more coding problems, please visit https://github.com/hoanhan101/algo.
Tagged: #leetcode, #algorithm