After solved 1000 medium leetcode found these patterns — Sliding Window, 2 Pointer, String

Following previous posted patterns : DFS , BFS, DP, Backtracking, Mono-stack ,Presum, Greedy .I will continue share what I have learned from leetcoding . with high rating problems .

This article will be Sliding Window , 2 Pointers , string(not a pattern just a category)

Lets start .

Sliding Window

Core Pattern

start, end = 0, 0
res=0
while end < length(arr or string):
    do_something(end)
    while decreasing_window_size(start):
        dosomething(start)
        start +=1
    res = max(res, end-start+1) # or min
    end+=1
return res

The idea is control a window<start, end> size dynamically . the goal usually is to find the max or min window size . during loop every time move the end to next position while trying keep the start ,if not then decreasing window by keep moving start position to next . track and update the window size .

Sample problems

3. Longest Substring Without Repeating Characters

Thought process . goal : #1 find longest , #2 without duplicate . for #1 need sliding window #2 need hashmap (dict) .so use start, end track window left and right . as long as no duplicate , keep moving the end to next, if there is dup, move start to right until no dup . update the result .

def lengthOfLongestSubstring(self, s: str) -> int:
    start, end = 0, 0
    arr = defaultdict(int)
    res=0
    while end < len(s):
        arr[s[end]]+=1
        while start < end and arr.get(s[end], 0) > 1:
            arr[s[start]]-=1
            start +=1
        res = max(res, end-start+1)
        end+=1
    return res

Another one . 209. Minimum Size Subarray Sum

Thought process. goal is to find the minimum window size when sum(<numbers in window>) ≥ target .use start and end to track window left and right ,keep adding nums[end] into sum, try to reduce the window (start+1) if possible (s-nums[start]≥ target) ,update result if window size < current result .

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    start, end=0, 0
    res=float('inf')
    s=0
    while end < len(nums):
        s += nums[end]
        while s>= target+nums[start]:
            s -= nums[start]
            start += 1
        if s >= target:
            res = min(res, end-start+1)
        end += 1
    return 0 if res == float('inf') else res

Usually when the problem about max or min length or count .could give sliding window a try. ask yourself what information need to keep track except the start and end index, then find out the condition of “decreasing window size” .

Btw, I have been asked 2 times sliding window problems in interview, both 1st round . maybe because these problems lines of code is short and good for interview. but to be honest in real life project, i have not used it to solve problem yet .

More sliding window problems

424. Longest Repeating Character Replacement

438. Find All Anagrams in a String

567. Permutation in String

1004. Max Consecutive Ones III

2 Pointer

Idea

Problem 1
xxxxxyyyyyzzzzzzzzzz
|                  |
left->          <- right

Problem2
ssstrrrrrinng1
|
pointer1->
ssttrrringggg2
|
pointer2->

Problem3
sssssstttrrrrring
|    |
slow |
     fast

3 cases.

#1 use left and right pointers start from 2 side of array or string , check when need to move left or right ;

#2 use 2 pointers to track 2 different array or string, decide when to move which pointer to next position;

#3 use slow and fast pointer ,each time move more steps on fast pointer than slow , see when they will meet . the classic sample is detect if there is cycle in linked list .

Sample problems

11. Container With Most Water

Thought process . 2 pointer case with a bit greedy thinking here. use 2 pointers start from left and right, when value[left] > value[right] move right (it does not help when move left) ; other wise ,move left .

def maxArea(self, height: List[int]) -> int:
    """
       maintein left and right index
       when height[left] > height[right]: right-1. else left + 1
    """
    l,r = 0, len(height)-1
    res =0
    while l<r:
        res = max(res, min(height[l], height[r]) * (r-l))
        if height[l]> height[r] :
            r -= 1
        else: 
            l += 1
    return res

Another one . 16. 3Sum Closest (3 color flag also similar)

Sort the array . use 3 pointers left, mid, right to track the sum (left+mid+right) . based on target > sum, target<=sum, move the mid, or right (explained in comments )

def threeSumClosest(self, nums: List[int], target: int) -> int:
    """ 
        Explaination :
        <-sorted(array)->
        |--|------------|
      left mid        right 
      3 sum = left+mid+right
      when 3sum > target:
      right-1 (left+1 or mid+1 will make it even bigger)
      else :will try mid+1 (left+1 case is covered in outside loop)
    """
    nums = sorted(nums)
    l,m,r = 0, 1, len(nums)-1
    res = nums[l]+nums[m]+nums[r]
    while l < len(nums)-1:
        m = l+1
        r = len(nums)-1
        t = nums[l]+nums[m]+nums[r]
            
        while m < r:
            three_sum = nums[l]+ nums[m] +nums[r]
            if abs(three_sum-target) < abs(res-target):
                res = three_sum
            if three_sum > target:
                r -= 1
            else:
                m += 1
        l += 1
    return res

More 2 pointer problem

264. Ugly Number II

524. Longest Word in Dictionary through Deleting

986. Interval List Intersections

1023. Camelcase Matching

String problems

String problems usually about regex matching and searching, or use hashmap or counter.

but in case you may be asked the same, which i had been asked to solve in an interview .

394. Decode String

When you see this problem . looks like it is stack ,but it’s not (it’s going to be slow if use stack) . could be using pure string manipulation . however it is actually a matching and replace problem, so regex usally the best option .

I list down all 3 solutions. i did #2 solution . then i found another solution in leetcode answers #3 which is even cleaner .

So when you be asked string problem, remember to give regex a try. sometimes it is a fast and clean.

1. when ']' parse previous string
def decodeString(self, s: str) -> str:
    i = 0
    while i<len(s):
        if s[i] == ']':
            j = i
            while s[j] != '[':
                j-=1
            s1 = s[j+1:i]
            times = ''
            k=j-1
            while k>=0 and s[k].isdigit():
                times=f'{s[k]}{times}'
                k-=1
            s2=int(times)*s1
            s=s[:k+1]+s2+s[i+1:]
            i=len(s2)+k
        i+=1
    return s
2. Use regex search (much cleaner)
def decodeString(self, s: str) -> str:
    pattern = '(\d+)\[([a-z]+)\]'
    while True:
        res = re.search(pattern, s)
        if not res:
            return s
        times, s1 = int(res[1]), res[2]
        s = s.replace(f'{times}[{s1}]', times*s1)
    return s
3. Use regex sub ( bit slower, but clearer)
def decodeString(self, s: str) -> str:
    pattern = '(\d+)\[([a-z]+)\]'
    while '[' in s:
        s = re.sub(pattern, lambda m: int(m.group(1))*m.group(2), s)
    return s

More string problems

318. Maximum Product of Word Lengths

880. Decoded String at Index

Conclusion

All 3 patterns i shared in this article have been asked in interviews (Sliding window : FANG, 2 Pointers : banking, String : Banking ) , 2 pointers is more like an idea instead of pattern ; for the string problems, keep regex in mind, the solution usually could be clean and fast in many cases.

Thanks for reading and happy leetcoding !