Array and Strings

인터뷰에서 배열 및 문자열 유형의 질문이 자주 제기되었습니다. 인터뷰 중에 만날 가능성이 큽니다.

권장 사항 : 그룹 아나그램, 반복 문자가없는 가장 긴 부분 문자열, 가장 긴 회문 부분 문자열 및 누락 된 범위.

Array and String type of questions were asked in interviews frequently. You will most likely encounter one during your interviews.

We recommend: Group Anagrams, Longest Substring Without Repeating Characters, Longest Palindromic Substring and Missing Ranges.

3Sum

Set Matrix Zeroes

Group Anagrams

Longest Substring Without Repeating Characters

Longest Palindromic Substring

Increasing Triplet Subsequence

Missing Ranges

15. 3Sum

leetcode.com/problems/3sum/

Medium

9219962Add to ListShare

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = [] Output: []

Example 3:

Input: nums = [0] Output: []

Constraints:

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!

Show Hint 2

For the two-sum problem, if we fix one of the numbers, sayx, we have to scan the entire array to find the next numberywhich isvalue - xwhere value is the input parameter. Can we change our array somehow so that this search becomes faster?

The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

투썸 문제 처럼 인터뷰에서는 투포인터 방식으로 접근하는것이 가장 이상적이다.

Approach 1: Two Pointers

We will follow the same two pointers pattern as in Two Sum II. It requires the array to be sorted, so we'll do that first. As our BCR is \mathcal{O}(n^2), sorting the array would not change the overall time complexity.

To make sure the result contains unique triplets, we need to skip duplicate values. It is easy to do because repeating values are next to each other in a sorted array.

If you are wondering how to solve this problem without sorting the array, go over the "No-Sort" approach below. There are cases when that approach is preferable, and your interviewer may probe your knowledge there.

After sorting the array, we move our pivot element nums[i] and analyze elements to its right. We find all pairs whose sum is equal -nums[i] using the two pointers pattern, so that the sum of the pivot element (nums[i]) and the pair (-nums[i]) is equal to zero.

As a quick refresher, the pointers are initially set to the first and the last element respectively. We compare the sum of these two elements to the target. If it is smaller, we increment the lower pointer lo. Otherwise, we decrement the higher pointer hi. Thus, the sum always moves toward the target, and we "prune" pairs that would move it further away. Again, this works only if the array is sorted. Head to the Two Sum II solution for the detailed explanation.

1 / 14

Algorithm

The implementation is straightforward - we just need to modify twoSumII to produce triplets and skip repeating values.

For the main function:
- Sort the input array nums.
- Iterate through the array:
  - If the current value is greater than zero, break from the loop. Remaining values cannot sum to zero.
  - If the current value is the same as the one before, skip it.
  - Otherwise, call twoSumII for the current position i.
For twoSumII function:
- Set the low pointer lo to i + 1, and high pointer hi to the last index.
- While low pointer is smaller than high:
  - If sum of nums[i] + nums[lo] + nums[hi] is less than zero, increment lo.
  - If sum is greater than zero, decrement hi.
  - Otherwise, we found a triplet:
    - Add it to the result res.
    - Decrement hi and increment lo.
    - Increment lo while the next value is the same as before to avoid duplicates in the result.
Return the result res.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if i == 0 or nums[i - 1] != nums[i]:
                self.twoSumII(nums, i, res)
        return res

    def twoSumII(self, nums: List[int], i: int, res: List[List[int]]):
        lo, hi = i + 1, len(nums) - 1
        while (lo < hi):
            sum = nums[i] + nums[lo] + nums[hi]
            if sum < 0:
                lo += 1
            elif sum > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1

Complexity Analysis

Time Complexity: \mathcal{O}(n^2). twoSumII is \mathcal{O}(n), and we call it n times.

Sorting the array takes \mathcal{O}(n\log{n}), so overall complexity is \mathcal{O}(n\log{n} + n^2). This is asymptotically equivalent to \mathcal{O}(n^2).
Space Complexity: from \mathcal{O}(\log{n}) to \mathcal{O}(n), depending on the implementation of the sorting algorithm. For the purpose of complexity analysis, we ignore the memory required for the output.

Further Thoughts

This is a well-known problem with many variations and its own Wikipedia page.

For an interview, we recommend focusing on the Two Pointers approach above. It's easier to get it right and adapt for other variations of 3Sum. Interviewers love asking follow-up problems like 3Sum Smaller and 3Sum Closest!

73. Set Matrix Zeroes

leetcode.com/problems/set-matrix-zeroes/

Medium

2983351Add to ListShare

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

If any cell of the matrix has a zero we can record its row and column number using additional memory. But if you don't want to use extra memory then you can manipulate the array instead. i.e. simulating exactly what the question says.

Hide Hint 2

Setting cell values to zero on the fly while iterating might lead to discrepancies. What if you use some other integer value as your marker? There is still a better approach for this problem with 0(1) space.

Hide Hint 3

We could have used 2 sets to keep a record of rows/columns which need to be set to zero. But for an O(1) space solution, you can use one of the rows and and one of the columns to keep track of this information.

Hide Hint 4

We can use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero.

Approach 2: O(1) Space, Efficient Solution

Intuition

Rather than using additional variables to keep track of rows and columns to be reset, we use the matrix itself as the indicators.

The idea is that we can use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero. This means for every cell instead of going to M+N cells and setting it to zero we just set the flag in two cells.

if cell[i][j] == 0 { cell[i][0] = 0 cell[0][j] = 0 }

These flags are used later to update the matrix. If the first cell of a row is set to zero this means the row should be marked zero. If the first cell of a column is set to zero this means the column should be marked zero.

Algorithm

We iterate over the matrix and we mark the first cell of a row i and first cell of a column j, if the condition in the pseudo code above is satisfied. i.e. if cell[i][j] == 0.
The first cell of row and column for the first row and first column is the same i.e. cell[0][0]. Hence, we use an additional variable to tell us if the first column had been marked or not and the cell[0][0] would be used to tell the same for the first row.
Now, we iterate over the original matrix starting from second row and second column i.e. matrix[1][1] onwards. For every cell we check if the row r or column c had been marked earlier by checking the respective first row cell or first column cell. If any of them was marked, we set the value in the cell to 0. Note the first row and first column serve as the row_set and column_set that we used in the first approach.
We then check if cell[0][0] == 0, if this is the case, we mark the first row as zero.
And finally, we check if the first column was marked, we make all entries in it as zeros.

1 / 18

In the above animation we iterate all the cells and mark the corresponding first row/column cell incase of a cell with zero value.

We iterate the matrix we got from the above steps and mark respective cells zeroes.

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        is_col = False
        R = len(matrix)
        C = len(matrix[0])
        for i in range(R):
            # Since first cell for both first row and first column is the same i.e. matrix[0][0]
            # We can use an additional variable for either the first row/column.
            # For this solution we are using an additional variable for the first column
            # and using matrix[0][0] for the first row.
            if matrix[i][0] == 0:
                is_col = True
            for j in range(1, C):
                # If an element is zero, we set the first element of the corresponding row and column to 0
                if matrix[i][j]  == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        # Iterate over the array once again and using the first row and first column, update the elements.
        for i in range(1, R):
            for j in range(1, C):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0

        # See if the first row needs to be set to zero as well
        if matrix[0][0] == 0:
            for j in range(C):
                matrix[0][j] = 0

        # See if the first column needs to be set to zero as well        
        if is_col:
            for i in range(R):
                matrix[i][0] = 0

Complexity Analysis

Time Complexity : O(M \times N)
Space Complexity : O(1)

leetcode.com/problems/group-anagrams/

3. Longest Substring Without Repeating Characters

leetcode.com/problems/longest-substring-without-repeating-characters/

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = "" Output: 0

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

Video Solution

Solution Article

Approach 1: Brute Force

Intuition

Check all the substring one by one to see if it has no duplicate character.

Algorithm

Suppose we have a function boolean allUnique(String substring) which will return true if the characters in the substring are all unique, otherwise false. We can iterate through all the possible substrings of the given string s and call the function allUnique. If it turns out to be true, then we update our answer of the maximum length of substring without duplicate characters.

Now let's fill the missing parts:

To enumerate all substrings of a given string, we enumerate the start and end indices of them. Suppose the start and end indices are i and j, respectively. Then we have 0 \leq i \lt j \leq n (here end index j is exclusive by convention). Thus, using two nested loops with i from 0 to n - 1 and j from i+1 to n, we can enumerate all the substrings of s.
To check if one string has duplicate characters, we can use a set. We iterate through all the characters in the string and put them into the set one by one. Before putting one character, we check if the set already contains it. If so, we return false. After the loop, we return true.

TLE

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        
        def allUnique(s: str, start: int, end: int):
            chars = set()
            for i in range(start, end):
                ch = s[i]
                if ch in chars:
                    return False
                chars.add(ch)
            return True
        
        for i in range(n):
            for j in range(i+1, n+1):
                if allUnique(s, i, j):
                    ans = max(ans, j - i)
        
        return ans

Complexity Analysis

Time complexity : O(n^3).

To verify if characters within index range [i, j) are all unique, we need to scan all of them. Thus, it costs O(j - i) time.

For a given i, the sum of time costed by each j \in [i+1, n] is

\sum_{i+1}^{n}O(j - i)

Thus, the sum of all the time consumption is:

O\left(\sum_{i = 0}^{n - 1}\left(\sum_{j = i + 1}^{n}(j - i)\right)\right) = O\left(\sum_{i = 0}^{n - 1}\frac{(1 + n - i)(n - i)}{2}\right) = O(n^3)
Space complexity : O(min(n, m)). We need O(k) space for checking a substring has no duplicate characters, where k is the size of the Set. The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m.

Approach 2: Sliding Window

Algorithm

The naive approach is very straightforward. But it is too slow. So how can we optimize it?

In the naive approaches, we repeatedly check a substring to see if it has duplicate character. But it is unnecessary. If a substring s_{ij} from index i to j - 1 is already checked to have no duplicate characters. We only need to check if s[j] is already in the substring s_{ij}.

To check if a character is already in the substring, we can scan the substring, which leads to an O(n^2) algorithm. But we can do better.

By using HashSet as a sliding window, checking if a character in the current can be done in O(1).

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. [i, j) (left-closed, right-open). A sliding window is a window "slides" its two boundaries to the certain direction. For example, if we slide [i, j) to the right by 1 element, then it becomes [i+1, j+1) (left-closed, right-open).

Back to our problem. We use HashSet to store the characters in current window [i, j) (j = i initially). Then we slide the index j to the right. If it is not in the HashSet, we slide j further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index i. If we do this for all i, we get our answer.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        chars = set()
        ans = i = j = 0
        while i < n and j < n:
            if s[j] in chars:
                chars.remove(s[i])
                i += 1
            else:
                chars.add(s[j])
                j += 1
                ans = max(ans, j - i)
        return ans

Complexity Analysis

Time complexity : O(2n) = O(n). In the worst case each character will be visited twice by i and j.
Space complexity : O(min(m, n)). Same as the previous approach. We need O(k) space for the sliding window, where k is the size of the Set. The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m.

Approach 3: Sliding Window Optimized

The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

The reason is that if s[j] have a duplicate in the range [i, j) with index j', we don't need to increase i little by little. We can skip all the elements in the range [i, j'] and let i to be j' + 1 directly.

Java (Using HashMap)

Here is a visualization of the above code.

Java (Assuming ASCII 128)

The previous implements all have no assumption on the charset of the string s.

If we know that the charset is rather small, we can replace the Map with an integer array as direct access table.

Commonly used tables are:

int[26] for Letters 'a' - 'z' or 'A' - 'Z'
int[128] for ASCII
int[256] for Extended ASCII

이걸로 해야해요~

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        mp = {}
        
        i = 0
        for j in range(n):
            if s[j] in mp:
                i = max(mp[s[j]], i)
            ans = max(ans, j - i + 1)
            mp[s[j]] = j + 1
            
        return ans

Complexity Analysis