Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

Review: TwoPointers Problems

Posted on January 18, 2018July 26, 2020 by braindenny

Two pointers problems



Basic Abstractions

Name Summary
two pointers – left/right  
two pointers – left/right  

Review: TwoPointers Problems

Review: TwoPointers Problems

Review: TwoPointers Problems

Review: TwoPointers Problems

Scenarios
Code Skeleton
Top Questions

Name Example

Key Points:

  • Time complexity evaluation: pointers back and forth? Minimum Size Subarray Sum
  • One loop or two loop?
  • “left<right” or “left<=right”? Strobogrammatic Number
## Blog link: https://code.dennyzhang.com/strobogrammatic-number
maps = [('0', '0'), ('1', '1'), ('8', '8'), ('6', '9'), ('9', '6')]
left, right = 0, len(num)-1
while left<=right:
    if (num[left], num[right]) not in maps: return False
    left, right = left+1, right-1
return True
  • Use range to change pointer, instead of manual ways. Minimum Window Substring
## Blog link: https://code.dennyzhang.com/minimum-window-substring
left, right = 0, 0
for right in range(0, len1):
    m1[s[right]] += 1
    if self.isTooSmall(m1, m2): continue
    # find a match, then check whether window too big
    while m1[s[left]] > m2[s[left]]:
        m1[s[left]] -= 1
        left += 1
    # find a candidate
    if min_len > right-left+1:
        min_len, res = right-left+1, s[left:right+1]
return res

Sliding window:

  • Whether left and right are included?

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups

See all twopointer problems: #twopointer

  • Review: TwoPointers Problems
  • LintCode: Reverse Array
  • LintCode: Delete Characters
  • LintCode: 3Sum II
  • LeetCode: Valid Triangle Number
  • LeetCode: Valid Palindrome
  • LeetCode: Two Sum IV – Input is a BST
  • LeetCode: Two Sum II – Input array is sorted
  • LeetCode: Two Sum
  • LeetCode: Sum of Square Numbers
  • LeetCode: Subarray Product Less Than K
  • LeetCode: Squares of a Sorted Array
  • LeetCode: Sort Colors
  • LeetCode: Sort Array By Parity
  • LeetCode: Reverse Only Letters
  • LeetCode: Replace the Substring for Balanced String
  • LeetCode: Remove Nth Node From End of List
  • LeetCode: Random Pick with Blacklist
  • LeetCode: Random Flip Matrix
  • LeetCode: Partition Labels
  • LeetCode: Move Zeroes
  • LeetCode: Minimum Size Subarray Sum
  • LeetCode: Merge Sorted Array
  • LeetCode: Meeting Scheduler
  • LeetCode: Longest Chunked Palindrome Decomposition
  • LeetCode: Long Pressed Name
  • LeetCode: Linked List Cycle II
  • LeetCode: Linked List Cycle
  • LeetCode: Last Substring in Lexicographical Order
  • LeetCode: K-diff Pairs in an Array
  • LeetCode: Fruit Into Baskets
  • LeetCode: Duplicate Zeros
  • LeetCode: DI String Match
  • LeetCode: Count Binary Substrings
  • LeetCode: Container With Most Water
  • LeetCode: Check If a String Can Break Another String
  • LeetCode: Bag of Tokens
  • LeetCode: Assign Cookies
  • LeetCode: 4Sum
  • LeetCode: 3Sum Smaller
  • LeetCode: 3Sum Closest
  • LeetCode: 3Sum

See more blog posts.

linkedin
github
slack

Post Views: 9
Posted in ReviewTagged #twopointer, review

Post navigation

Review: Interval Problems
LeetCode: Walls and Gates

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.