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

5 min readMar 26, 2022

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 .

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

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 s2. 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 s3. 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

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 !

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

Sliding Window

2 Pointer

String problems

Conclusion

Written by LORY