1
2
3
4
5
6
7

class Solution:
    def old_new_state(self, arr):
        # initialize states
        old, new = default_val1, default_val2
        for item in arr:
            # process current element with old state
            old, new = new, self.some_func(item, old)

1
2
3
4
5
6
7

# Each number is the sum of the two preceding ones, starting from 0 and 1.
class Solution:
    def fibonacci(self, n: int) -> int:
        a, b = 0, 1
        for i in range(n + 1):
            a, b = b, a + b
        return a

1
2
3
4
5
6
7
8

# Determine the maximum amount of money you can steal tonight 
# without robbing adjacent houses.
class Solution:
    def rob(self, nums: 'List[int]') -> int:
        last, now = 0, 0
        for i in nums:
            last, now = now, max(last + i, now)
        return now

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def slow_fast_runner(self, arr):
        # initialize slow runner
        slow = arr[0]   
        
        # fast-runner grows each iteration generally
        for fast in range(arr):     
            #slow-runner grows with some restrictions
            if self.slow_condition(slow):
                slow = slow.next    # slow += 1

            # process logic before or after pointers movement
            self.some_func(slow, fast)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next: return False
        
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
            if slow == fast: return True
            
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people = sorted(people)
        i, j, res = 0, len(people)-1, 0
        while i <= j:
            if people[i] + people[j] <= limit:
                i = i + 1
            j = j - 1
            res += 1
            
        return res  

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# Given a sorted array nums, remove the duplicates in place such that 
# each element appear only once and return the new length.
class Solution:
    def removeDuplicates(self, nums: 'List[int]') -> int:
        if not nums: return 0
        slow = 0
        for fast in range(1, len(nums)):
            # if current element is not duplicate, 
            # slow runner grows one step and copys the current value
            if nums[slow] != nums[fast]:
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def left_right_boundary(self, arr):
        left, right = 0, len(arr) - 1
        while left < right:
            # left index moves when satisfy the condition
            if self.left_condition(left):
                left += 1
            # right index move when satisfy the condition
            if self.right_condition(right):
                right -= 1
            # process logic before or after pointers movement
            self.some_func(left, right)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# Given an array of integers that is already sorted in ascending 
# order, find two numbers such that they add up to a specific target number.
class Solution:
    def twoSum(self, numbers: 'List[int]', target: 'int') -> 'List[int]':
        left, right = 0, len(numbers) - 1
        while left < right:
            if numbers[left] + numbers[right] == target:
                return [left + 1, right + 1]
            if numbers[left] + numbers[right] < target:
                left += 1
            else:
                right -= 1
        return [0, 0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def pointers_from_two_seq(self, arr1, arr2):
        # init pointers
        p1, p2 = 0, 0       # or seq1[0], seq2[0]

        while p1 < len(arr1) and p2 < len(arr2):    # or other condition
            # p1 index moves when satisfy the condition
            if self.p1_condition(p1):
                p1 += 1         # or p1 = next(seq1)
            # p2 index move when satisfy the condition
            if self.p2_condition(p2):
                p2 += 1         # or p2 = next(seq2)
            # process logic before or after pointers movement
            self.some_func(p1, p2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Design a class which receives a list of words in the constructor 
# and implements a method that takes two words, word1 and word2, and 
# returns the shortest distance between these two words in the list.
class WordDistance:
    def __init__(self, words: 'List[str]'):
        self.locations = defaultdict(list)
        # Prepare a mapping from a word to all it's locations (indices).
        for i, w in enumerate(words):
            self.locations[w].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        loc1, loc2 = self.locations[word1], self.locations[word2]
        l1, l2 = 0, 0
        min_diff = float("inf")

        # Until the shorter of the two lists is processed
        while l1 < len(loc1) and l2 < len(loc2):
            min_diff = min(min_diff, abs(loc1[l1] - loc2[l2]))
            if loc1[l1] < loc2[l2]:
                l1 += 1
            else:
                l2 += 1
        return min_diff

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def sliding_window(self, arr):
        start, end = 0, 0
        while end < len(arr):
            # end pointer grows in the outer loop
            end += 1
            
            # start pointer grows with some restrict
            while self.start_condition(start):
                # process logic before pointers movement
                self.some_func(start, end)
                # start grows in the inner loop
                start += 1
                
            # or process logic after pointers movement
            self.some_func(start, end)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

# Given an array of positive integers nums and a positive integer 
# target, return the minimal length of a contiguous subarray of 
# which the sum is greater than or equal to target.
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums or len(nums) == 0:
            return 0
        
        l, r = 0, 0
        res = len(nums) + 1
        add = 0

        while r < len(nums):
            add += nums[r]
        r += 1                   # Upsizing the window
            while add >= target: # Downsizing the window iteratively
                res = min(res, r - l)
                add -= nums[l]
                l += 1
            
        return res if res != len(nums) + 1 else 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Given a string s and an integer k, return the maximum number of vowel 
# letters in any substring of s with length k.
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        if not s or len(s) == 0 or len(s) < k:
            return 0
        
        vl = set(['a', 'e', 'i', 'o', 'u']) # Quick for search
        i, j = 0, 0
        res, tmp = 0, 0
        while j < len(s):
            if j - i < k:          
            # Get the number of vowel letters in the first sliding window
                if s[j] in vl:
                    tmp += 1
                    res = tmp
                j += 1
            else:
                # Pop the first item
                if s[i] in vl:
                    tmp -= 1
                i += 1
                    
                # Add the next item
                if s[j] in vl:
                    tmp += 1
                    
                res = max(tmp, res)
                j += 1
        return res