LeetCode Problems

[kymr]

• https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
• https://leetcode.com/problems/permutations/
• https://leetcode.com/problems/sudoku-solver/
• https://leetcode.com/problems/merge-k-sorted-lists/
• https://leetcode.com/problems/reverse-linked-list-ii/
• https://leetcode.com/problems/unique-binary-search-trees/
• https://leetcode.com/problems/binary-tree-postorder-traversal/
• https://leetcode.com/problems/number-of-islands/
• https://leetcode.com/problems/kth-smallest-element-in-a-bst/
• https://leetcode.com/problems/course-schedule/
• https://leetcode.com/problems/majority-element/
  • 과반수 득표
• https://leetcode.com/problems/course-schedule-ii/
• https://leetcode.com/problems/burst-balloons/
• https://leetcode.com/problems/longest-increasing-subsequence/
• https://leetcode.com/problems/flatten-nested-list-iterator/
• https://leetcode.com/problems/insert-delete-getrandom-o1/
• https://leetcode.com/problems/hamming-distance/
• https://leetcode.com/problems/132-pattern/
• https://leetcode.com/problems/maximum-binary-tree/
• https://leetcode.com/problems/out-of-boundary-paths/
• https://leetcode.com/problems/generate-random-point-in-a-circle/
• https://leetcode.com/problems/top-k-frequent-words/
• https://leetcode.com/problems/accounts-merge/
• https://leetcode.com/problems/longest-univalue-path/
• https://leetcode.com/problems/soup-servings/
• https://leetcode.com/problems/most-profit-assigning-work/
• https://leetcode.com/problems/koko-eating-bananas/solution/
• https://leetcode.com/problems/array-of-doubled-pairs/
• https://leetcode.com/problems/minimum-area-rectangle-ii/
  • diagonal has same length
  • cross center position
• https://leetcode.com/problems/is-subsequence/
  • TreeSet for follow up
  • ceiling, floor, headSet, subSet, tailSet
• https://leetcode.com/problems/erect-the-fence/
  • Convex Hull
  • Gift Wrapping aka Jarvis March
  • Graham scan
• https://leetcode.com/problems/is-graph-bipartite/
  • 2 colors problem
• https://leetcode.com/problems/valid-parenthesis-string/submissions/
  • Deque
  • 2 way validation
• https://leetcode.com/problems/zuma-game/
• https://leetcode.com/problems/largest-plus-sign/
• https://leetcode.com/problems/lfu-cache/
  • HashMap for cache
  • List of LinkedHashSet for frequency management
  • add to last
  • remove from first
  • update lowestFrequency
• https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
• https://leetcode.com/problems/path-sum-iii
• https://leetcode.com/problems/redundant-connection-ii/
  • count indegree for each node
  • generate Map<Node, Set> for edges
  • try to remove an edge from last to first
  • check the graph is valid (no 2 indegree & no cycle)
  • topological sort
• https://leetcode.com/problems/reverse-pairs
  • Brute Force
  • Sequential recurrence relation
  • Partition recurrence relation
  • T(0, n-1) = T(0, m) + T(m+1, n-1) + C
  • The order of subarray is not important.
  • Two Pointer Technic
  • Merge Sort
  • nested while loop for searching
• https://leetcode.com/problems/range-sum-of-bst
• https://leetcode.com/problems/strong-password-checker/
• https://leetcode.com/problems/search-a-2d-matrix/
• https://leetcode.com/problems/clone-graph
• https://leetcode.com/problems/maximum-frequency-stack
• https://leetcode.com/problems/shifting-letters/
• https://leetcode.com/problems/design-hashset
• https://leetcode.com/problems/check-completeness-of-a-binary-tree/
• https://leetcode.com/problems/utf-8-validation
• https://leetcode.com/problems/maximum-gap/
  • Bucket Sort
  • max - min
  • N - 1
  • gap = Math.ceil((max - min) / (N - 1))
  • save only min max
  • Radix Sort
• https://leetcode.com/problems/set-matrix-zeroes
• https://leetcode.com/problems/target-sum/submissions/
• https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree
  • solved
  • draw graph
  • dfs
  • parentMap
  • traverse
  • percolate distance
• https://leetcode.com/problems/super-ugly-number/
  • new ugly number = min(prime * previously generated ugly)
  • update indexes for each prime value (candidate)
• https://leetcode.com/problems/most-stones-removed-with-same-row-or-column
  • stones number - islands number
  • DFS
  • Union Find
• https://leetcode.com/problems/counting-bits/
  • find patterns for each 2^n
  • [lo, mid)
  • [mid, hi)
  • hi
• https://leetcode.com/problems/replace-words
• https://leetcode.com/problems/distribute-coins-in-binary-tree
• https://leetcode.com/problems/race-car
  • dp
  • dist = 2^n - 1
  • 3 cases
  • target is (2^n - 1)
  • pass target and back
  • Go as far as possible and back and go back again
    • n - 1 => m => race left
• https://leetcode.com/problems/longest-turbulent-subarray/
  • took time to debug overflow issue
• https://leetcode.com/problems/reveal-cards-in-increasing-order/
  • understanding problem rule reverse order;
  • use Deque LinkedList
• https://leetcode.com/problems/making-a-large-island
  • dfs
  • set idx
  • increase island area size
  • handling edge case (no island)
  • return 1
  • for each 0
  • sum each adjacent island's size
  • check it is redundant
  • return max
• https://leetcode.com/problems/single-number-ii/
• https://leetcode.com/problems/longest-palindromic-substring
• https://leetcode.com/problems/range-sum-query-mutable/
  • segment tree
• https://leetcode.com/problems/h-index-ii/
• https://leetcode.com/problems/find-k-th-smallest-pair-distance/
  • binary search
  • count distance pair
• https://leetcode.com/problems/candy
  • check asc from the first to last
  • check asc from the last to first
  • select max
• https://leetcode.com/problems/subarray-sum-equals-k
  • cum sum => n^2
  • h ashmap cum sum => n
  • save cumSum count to map
  • start with (0, 1)
  • increase the count of sum - k exist
• https://leetcode.com/problems/global-and-local-inversions
  • There is no global inversion case, but local
  • loop and keep max value
• https://leetcode.com/problems/patching-array/
  • array is already sorted
  • check point from 1 until n
  • compare current value of nums to point
  • point < num
  • patch value
  • point jump to doubled, cause prev values of point already validated.
  • num <= point
  • point jump to point + num, and increase index, same reason
• https://leetcode.com/problems/binary-string-with-substrings-representing-1-to-n/
  • doesn't need to check all values
  • values greater than mid value contains small values
• https://leetcode.com/problems/binary-tree-cameras/
  • post-order traversal
  • leaf return 1 (no camera)
  • any children node return 1 then set the camera and return 0
  • any children node has camera then return 0 or return 1
  • handling root case outside traversal
  • count camera

[kymr]

100 문제 돌파 (2019-02-03)

[kymr]

150 문제 돌파 (2019-04-05)

[kymr]

• https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/
  • inside
  • < L
  • R <
• https://leetcode.com/problems/valid-triangle-number/
  • triangle condition
  • longest edge - loop from last to 2
  • check 2 other edge left most - 0, right most - longest-1
  • condition is met increase count, right --
  • if not, left++
• https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters
  • divide & conquer with helper (char[], start, end, k)
  • return 0;
  • return Math.max(left, right);
  • return right - left;
  • sliding window
  • iterate through unique letter 1 to 26
  • counts for each letter
  • left, right point
    • add until unique letter is less than equal u
    • remove until unique letter is greater than u
  • check unique count
  • check kOrMore count
• https://leetcode.com/problems/score-after-flipping-matrix/
  • maximize left most column
  • sum from left column to right column
• https://leetcode.com/problems/decoded-string-at-index/
  • loop from first to last
  • letter - size++
  • digit - size * digit
  • loop from last to first
  • K % size
  • if K == 0 then return last letter
  • digit - size / digit
  • letter - size--
• https://leetcode.com/problems/prison-cells-after-n-days
  • state could have cycle.
• https://leetcode.com/problems/flip-equivalent-binary-trees/
  • solved with hashMap
  • another) traverse tree1.LR, tree2.LR || tree1.LR, tree2.RL
• https://leetcode.com/problems/total-hamming-distance/
  • check count for each bit for each num
• https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/
  • cur = 1, k = k - 1
  • steps = (cur, cur + 1)
  • cur++ or cur *= 10
• https://leetcode.com/problems/smallest-integer-divisible-by-k
  • if multiple of 2 or 5 : -1
  • r = (r * 10 + 1) % K
• https://leetcode.com/problems/map-sum-pairs/
  • TreeMap or TreeSet
  • headSet(), tailSet(), subSet()
• https://leetcode.com/problems/queue-reconstruction-by-height/
  • sort (h desc, k asc)
  • insert to list with index k
• https://leetcode.com/problems/sliding-puzzle
  • bfs
• https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
• https://leetcode.com/problems/delete-operation-for-two-strings/
  • DP
• https://leetcode.com/problems/optimal-division/
  • elements are positive integers.
  • X1 is always numerator, X2 is always denominator
  • (X1 / X2) * Y
  • to maximize Y, (X1 X3 X4 ... Xn) / X2
  • which one is equal to X1 / (X2 / X3 / X4 / ... / Xn)
• https://leetcode.com/problems/additive-number/
  • i to {1..n/2}
  • j to {1..Math.max(i, j) <= N - i - j}
• https://leetcode.com/problems/implement-rand10-using-rand7/
  • 7 x 7 matrix
  • map values to 1 to 10;
  • row (rand7) x col (rand7)
  • retry if row x col > 40;
  • col + (row - 1) * 7 = (1 ~ 40)
  • 1 + (idx - 1) % 10
• https://leetcode.com/problems/maximum-swap/
  • count digit
  • from the first digit to the last.
  • check swappable digit exists (9 to digit + 1)
  • if digit is exist, find the right most loc
  • swap
• https://leetcode.com/problems/exam-room/
  • TreeSet
  • init dist = first()
  • d = (cur - prev) / 2
  • if d > dist
  • if (N - 1 - last) > dist
• https://leetcode.com/problems/decode-ways
  • DP
  • M[n] = 1
  • M[n-1] = s.charAt(n-1) == '0' ? 0 : 1
  • n-2..0
  • 0 - skip
  • <= 26 - M[i+1] + M[i+2]
  • else - M[i+1]
• https://leetcode.com/problems/set-intersection-size-at-least-two
  • sort array
  • for each interval, contains at least 2
  • check from last to first
  • for each start to start+leftCnt
    • for each 0 to current
    • if (value <= interval.end), leftCnt—
    • result++
• https://leetcode.com/problems/lru-cache/submissions/
  • class Node
  • key
  • value
  • pre
  • next
  • variables
  • nodeMap
  • head
  • tail
  • capacity
  • helper method
  • addToHead
  • removeLink
• https://leetcode.com/problems/permutation-in-string/
  • count for each char of s1
  • count for each char of substring of s2 which has same length to s1
  • slide-window and check cnt1 < cnt2 for each char
• https://leetcode.com/problems/pancake-sorting/
  • pick largest value and send it to last
  • keep indexMap
  • for i N..1
  • flip it twice (index, value) to locate largest value to last
  • update indexMap for j 1..i-1
    • i_index, j_index, i_value
    • i_index < j_index or else
• https://leetcode.com/problems/find-duplicate-file-in-system/
• https://leetcode.com/problems/push-dominoes
  • input = ‘L’ + input + ‘R’
  • 4 cases
  • L...L => LLLLL
  • R...R => RRRRR
  • L...R => L...R
  • R...L => RR.LL or RRLL
  • i = 0; j = 1, j < length
  • change middle values
• https://leetcode.com/problems/remove-invalid-parentheses
  • count (remove-L, remove-R)
  • backtrack + dfs
  • s, i, ret (hash), sb, l, r, open
  • fail case (l, r, open)
  • complete case (s.length == i)
  • traverse case
    • (
    • remove
    • not remove
    • )
    • remove
    • not remove
    • else
    • traverse
  • stringbuilder init (setLength())
• https://leetcode.com/problems/longest-consecutive-sequence
  • Group
  • HashMap minGroup, maxGroup
  • merge
  • But, it could be possible with single HashMap (num, size)
  • left, right
  • update num, num - left, num + right
• https://leetcode.com/problems/first-bad-version/
  • binary search
  • to find first (max = true, min false)
• https://leetcode.com/problems/sum-of-subsequence-widths
  • the order of arrays doesn’t matter. (sort)
  • ret += A[i] maximum => subsequence count : 2^i
  • ret -= A[i] minimum => subsequence count : 2^(N-i-1)
  • (ret + mod) % mod for negative
• https://leetcode.com/problems/binary-subarrays-with-sum/
  • TODO

[kymr]

200 문제

[kymr]

• https://leetcode.com/problems/repeated-string-match/
  • rolling
  • head + repeating + tail
• https://leetcode.com/problems/concatenated-words/
  • class TrieNode
  • HashMap<Character, TrieNode> children = new HashMap<>();
  • String content
  • isWord()
  • build TrieNode
  • backtrack from the root
  • branching if concatenated result found
  • child.isWord()
    • check result on last char
    • start new word
    • keep tracking
  • !child.isWord()
    • keep tracking
• https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii
  • binary search
  • check 4 cases (lo-mid, mid-hi)
• https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
  • backtracking
  • memoization
• https://leetcode.com/problems/longest-repeating-character-replacement
  • A to Z
  • try to count longest with sliding window
• https://leetcode.com/problems/shortest-path-visiting-all-nodes
  • mask is represented as nodes already visited
  • State (node, mask)
  • init dp[i] MAX_VALUE, dp[i][1<<i] = 0
  • for each nodes bfs traverse
  • find shortest for all dp[i][all visited mask]
• https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/
  • traverse with adding last bit 0, 1 + pruning

[kymr]

• https://leetcode.com/problems/shortest-common-supersequence
  • dp[][] edit-distance insert only
  • build string reverse order, from dp[m][n] to dp[0][0]
• https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
  • binary search
  • left side is ordered
  • right side is ordered
  • else
• https://leetcode.com/problems/interleaving-string/
  • solved with backtracking
  • another solution is DP
• https://leetcode.com/problems/median-of-two-sorted-arrays
  • binary-search with recursive
  • find kTh value
  • A is exhausted, return value in B
  • B is exhausted, return value in A
  • k == 1 (first value, Math.min(A-first, B-first)
  • aMid, bMid, if not in range (start + k/2 - 1), then MAX_VALUE, in range set Value
  • aMid < bMid
    • getKth(A, startA + k/2, B, startB, k - k/2)
  • or else
    • getKth(A, startA, B, startB + k/2, k - k/2)
• https://leetcode.com/problems/bulb-switcher-ii
  • 4 case => 1x2x3 => 6 bits
  • 6 bits case
  • l1 = 1 + a + c + d
  • l2 = 1 + a + b
  • l3 = 1 + a + c
  • l4 = 1 + a + b + d = l1 + l2 + l3
  • l5 = 1 + a + c = l3
  • l6 = 1 + a + b = l2
  • 3 bits case
• https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows
  • row to String
  • xor with first value
  • Map<String, Count> to count
  • return max
• https://leetcode.com/problems/find-and-replace-pattern/
  • normalize word
• https://leetcode.com/problems/hand-of-straights/
  • Queue State
• https://leetcode.com/problems/find-the-shortest-superstring
  • calculate dist[i][j] = appendRequiredLength(A[i], A[j])
  • dp[1<N][N]
  • path[1<N][N]
  • for i 1..1<N
  • initialize array to max
  • for j 0..N
    • if j is belong to i
    • prev = i - (1 << j)
    • prev could be 0, if j is start
    • else, for k 0..N
    • dp[prev][k] is valid path && dp[prev][k] + dist[k][j] < dp[i][j]
    • save dp[i][j], path[i][j]
    • if i is last & dp[i][j] < min
    • last to j
    • min
  • recover paths reverse way with stack
  • build result string

[kymr]

• https://leetcode.com/problems/largest-divisible-subset/
  • solved with dp
  • LIS
  • save path which is longest
• https://leetcode.com/problems/rotate-list/
• https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes
  • post order
  • return DeepestNode to parent (left, right, self)
• https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60
  • cumulative
  • keep count of (t mod 60)
  • add count which value is (t + x) % 60 = 0
  • (((60 - t) % 60) + 60) % 60
• https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
  • Using TreeMap with <cumulated area size, rect index>
• https://leetcode.com/problems/split-array-into-consecutive-subsequences/
  • count map
  • for each num
  • if count == 0
  • else if tails > 0
    • extend tails
  • else if num + 1 > 0 num + 2 > 0
    • minus num + 1, num + 2
    • increase tail num + 3
  • else
    • impossible
• https://leetcode.com/problems/permutation-sequence/
  • build from first to last
  • case count
• https://leetcode.com/problems/expressive-words/
  • class Group (chat c, int cnt, boolean stretchy)
• https://leetcode.com/problems/palindrome-partitioning/
  • find palindrome with dp boolean[][]
  • dfs
• https://leetcode.com/problems/product-of-array-except-self/
  • Left Array
  • Right Array
  • ret
• https://leetcode.com/problems/shortest-bridge/
  • dfs color the island
  • find shortest with calculating manhattan distance
• https://leetcode.com/problems/minimum-time-difference/
  • to minute integer
  • sort
  • min diff

[kymr]

• https://leetcode.com/problems/asteroid-collision/
• https://leetcode.com/problems/data-stream-as-disjoint-intervals/
  • TreeMap<start, end>
• https://leetcode.com/problems/maximal-rectangle/
  • int[][] width, int[][] height consequence 1s count
  • calculate area for 1 to height, Math.min(width, newWidth) * h
• https://leetcode.com/problems/combination-sum-ii/
  • backtracking
• https://leetcode.com/problems/house-robber/
  • dp
• https://leetcode.com/problems/reverse-nodes-in-k-group
• https://leetcode.com/problems/score-of-parentheses/
• https://leetcode.com/problems/simplify-path/
• https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
  • traverse level order with next pointer
• https://leetcode.com/problems/pacific-atlantic-water-flow/
  • Pacific[][], Atlantic[][]
  • dfs
• https://leetcode.com/problems/minimize-malware-spread/
  • DFS to find the max size of network that has only one malware node
• https://leetcode.com/problems/gray-code/
  • solved with backtracking solution (bit 0 to 1, 1 to 0)
  • another solution which is effective
  • add next sequence from previous sequence.
  • for example 2 to 3 is
    • 00,01,11,10 -> (000,001,011,010) (110,111,101,100)
    • 00 == 000, 01 == 001, 11 == 011, 10 == 010
    • highest bit different
    • order is backward
  • execute from 0 to n iteratively
• https://leetcode.com/problems/unique-substrings-in-wraparound-string/
  • isConsequence method
  • int[] exist = new int[26];
  • two pointer & count it when it is not consequence
• https://leetcode.com/problems/cheapest-flights-within-k-stops/
  • Map of Map (src, dest, price)
  • PriorityQueue (price, src, stopsLeft)
  • init offer(0, src, K+1)
  • traverse greedy way
• https://leetcode.com/problems/partition-to-k-equal-sum-subsets
  • it should be sum % k
  • each group should be sum / k
  • easily design likes dfs & backtracking
  • but inside there is more effective way to traverse
  • curSum, round, visited, target, startIndex
  • sort the array, before traversing
  • initialize the start index of loop to startIndex, then loop to 0
  • because recursion (dfs) of it with new curSum(curSum + nums[i]), next candidate of nums[i] should be smaller than before.
• https://leetcode.com/problems/find-right-interval/
  • solved with TreeSet
  • binarySearch could be possible
• https://leetcode.com/problems/can-i-win/
  • dfs with memoization
  • memo boolean[] visited
• https://leetcode.com/problems/grumpy-bookstore-owner/
  • sliding window
• https://leetcode.com/problems/remove-nth-node-from-end-of-list/
  • two pointer
• https://leetcode.com/problems/contains-duplicate-iii/
  • solved with TreeMap

[kymr]

• https://leetcode.com/problems/perfect-rectangle/submissions/
  • solved with brute-force
  • check area is equal to sum of each area
  • check overlapping each other
  • more efficient way
  • check wide area is equal to sum of each area
  • keep the set of point (x, y) which one is not exist before, if it is exist then remove it from set
  • if it is perfect rectangle, then the count of points should be 4, and it is same with the point of wide rectangle
• https://leetcode.com/problems/count-of-smaller-numbers-after-self/
  • BST - node (val, leftCnt, dup)
  • for N-1..0 insert nums[i] to BST
  • node == null, add new node and set ret[i]
  • node.val == val, increase node.dup and set ret[i]
  • node.val < val, insert node.right with increased curSum (curSum+node.leftCnt+node.dup)
  • node.val > val, increase node.leftCnt and insert node.left
• https://leetcode.com/problems/k-inverse-pairs-array/
  • solved with dp[n+1][k+1]
  • from 1 to n, add new i to each space
• https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
  • binary search
• https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
  • recursive way
  • build(pre-index, post-index, count)
  • count == 0 null, count == 1 just 1 node
  • devide : pre[pre-index + 1] == post[post-index - 1 + loop]
  • left : pre-index + 1, post-index, devide
  • right : pre-index + 1 + devide, post-index + devide, count - devide - 1
• https://leetcode.com/problems/super-washing-machines/
  • for each machines, cur should be mean value
  • [0, 0, 11, 5], [-4, -4, 7, 1]
  • cumulative moves : max is 8
  • [-4, -4, 7, 1]
  • [0, -8, 7, 1]
  • [0, 0, -1, 1]
  • [0, 0, 0, 0]
  • peak of machine : 7 (11 to 4), cause moving is possible once at specific machine for each turn
  • max(cumulative moves, peak of machine)
• https://leetcode.com/problems/minimum-number-of-refueling-stops/
  • dp
  • dp[i] means longest distance to go with i times stop
  • for each station, update dp
  • priority-queue
  • PQ with liters of fuel to charge
  • loop while fuel < target
  • if station-i in range of current fuel, then offer the fuel to PQ
  • if PQ is empty, then cannot reach
  • charge maximum fuel which is possible from PQ
• https://leetcode.com/problems/escape-the-ghosts/
  • manhattan distance
• https://leetcode.com/problems/trapping-rain-water-ii/
  • init outside cells to priority queue
  • poll lowest height cell, and update max-height
  • if neighbor cell is not visited yet, then offer to pq
  • if neighbor cell’s height is lower than max-height, then increase trap
• https://leetcode.com/problems/find-the-duplicate-number/
  • two pointer
  • same as find the first node which is the start point of cycle in the linked-list

[kymr]

• https://leetcode.com/problems/car-fleet/
  • sort by pos desc
  • traceable by time
• https://leetcode.com/problems/count-the-repetitions/
  • for each character of s1, build-map int[idx][char] to point next index
• https://leetcode.com/problems/peeking-iterator/
• https://leetcode.com/problems/k-similar-strings/
  • BFS with Queue
  • for each step, loop all items from queue
  • find the first index of string which is not equal
  • swap to char which is not equal at the index and the char is looking for
  • if A == B return step, or offer it to queue
• https://leetcode.com/problems/special-binary-string/
  • It is like Valid-Parentheses
  • if it is VP (10 or 1100), then maximize mid-part of it (1M0) with recursion
  • add the maximized resut to the list
  • Sort the List by lexicographically desc order
  • join the list
• https://leetcode.com/problems/friend-circles/
  • dfs with int[] visited
• https://leetcode.com/problems/random-flip-matrix/
  • Map<Integer, Integer> to keep (selected-value, skipped-value)
  • random.nextInt(leftSize)
  • shuffle selected-value & leftSize (save to map)

[kymr]

[kymr]

• https://leetcode.com/problems/the-skyline-problem/
  • Point(x, y)
  • add all the left point and right point of rectangles to ArrayList<> points
  • Sort point
  • x asc
  • left first then right
  • (left) ? y desc : y asc
  • (Other way) Sort point
  • if Left then set y as minus y
  • then x asc, y asc
  • PriorityQueue height desc order
  • prev to 0
  • for each points
  • if left, then offer to pq
  • if right, then remove from pq
  • get current peek from pq
  • if (current != peek), then add Point (current x, peek) to results
• https://leetcode.com/problems/longest-arithmetic-sequence/
  • List<Map<Integer, Integer>> maps (index, diff, cnt)
  • for i [1, N-1]
  • new Map<diff, cnt>
  • for j [0, i-1]
    • map.put(diff, maps.get(j).getOrDefault(diff, 1))
• https://leetcode.com/problems/intersection-of-two-linked-lists/
  • two pointer
  • while (nodeA != nodeB)
  • nodeA is null, then set it to headB
  • nodeB is null, then set it to headA
  • if intersection exists
  • they meet at intersection at most 1 time traverse, cause x + y + z = y + x + z
  • else
  • they meet at each others null end point
• https://leetcode.com/problems/sliding-window-maximum/
  • int[] left max val until [i], reset for each k
  • int[] right max val until [i], reset for each k
  • Math.max(left, right)

[kymr]

• https://leetcode.com/problems/3sum-closest/
  • Arrays.sort(nums)
  • for i 0 to N - 3
  • two pointer
  • start i + 1, end N - 1
  • if sum < target start++, else end--
• https://leetcode.com/problems/3sum/
  • Arrays.sort(nums)
  • for i 0 to N - 3
  • two pointer
  • start i + 1, end N - 1
  • if sum is 0, add triplet to result and start++, end-- until num is changed
  • else if sum < 0, start++
  • else if sum > 0, end--
• https://leetcode.com/problems/4sum/
  • using 3sum
• https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
  • two pointer
• https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
  • O(n) & O(n) : Level order traversal with Queue
  • O(n) & O(1) : Level order traversal with next pointer, and build next level next pointer
• https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
  • dp with 3 state
• https://leetcode.com/problems/majority-element-ii/
  • It could have 2 elements at most to satisfy restriction (more than n / 3 times)
  • keep 2 spots (value, cnt)
  • loop
  • if value exists, then cnt++
  • else if spot is empty (cnt == 0), then claim
  • else -1 each items
  • loop
  • check 2 items appear more than n / 3
• https://leetcode.com/problems/distribute-coins-in-binary-tree/
  • traverse post-order
• https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
  • iterate String and build Queue (level & TreeNode)
  • iterate Queue & using Stack
  • if the currentNode’s level is higher than Stack.peek(), then left and push to Stack
  • if the currentNode’s level is lower than or equal to Stack.peek(), then pop from Stack until it is satisfied, then right and push to Stack
• https://leetcode.com/problems/combination-sum-iv/
  • dp[0] to dp[target]
• https://leetcode.com/problems/maximum-length-of-pair-chain/
  • solved with dp O(N^2)
  • greedy is O(NlogN)
• https://leetcode.com/problems/orderly-queue/
  • K > 1, then sort
  • K == 1, rotate string N cases. choose minimum
• https://leetcode.com/problems/maximum-product-of-word-lengths/
  • convert words to int[] chars array, and check N^2
  • (efficient) convert words to int (bit for each char), and check N^2 with &
• https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
  • int[][] B & S = new int[len][k+1]
  • B[i][j] = Math.max(B[i-1][j], S[i-1][j] - prices[i])
  • S[i][j] = Math.max(S[i-1][j], B[i-1][j-1] + prices[i])
• https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/
  • array A => cumulative sum array
  • Initialize
  • lMax (0~L-1)
  • mMax (0~M-1)
  • for i [L+M, N-1]
  • lMax = Math.max(lMax, i-L-M+1 to i-M)
  • mMax = Math.max(mMax, i-L-M+1 to i-L)
  • max = Math.max(max, Math.max(lMax + [i-M+1, i], mMax + [i-L+1, i]))
• https://leetcode.com/problems/my-calendar-i/
  • TreeMap
• https://leetcode.com/problems/add-two-numbers-ii/
  • Stack
• https://leetcode.com/problems/search-a-2d-matrix-ii/
  • solved with dfs
  • more efficient version
  • start from right up corner
  • if target is lesser, col—;
  • if target is greater, row++;
• https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
  • two pointers
• https://leetcode.com/problems/convert-to-base-2/
  • same as base2, but after divide negate it
  • N & 1, then -(N >> 1)
• https://leetcode.com/problems/maximal-square/
  • dp[R+1][C+1]
  • dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1
• https://leetcode.com/problems/daily-temperatures/
  • stack
• https://leetcode.com/problems/rank-scores/
  • rank variable

[kymr]

• https://leetcode.com/problems/sum-of-distances-in-tree/
  • neighbor (x, y)
  • ans[x] = ans[sub-x] + ans[sub-y] + count[y]
  • ans[y] = ans[sub-x] + ans[sub-y] + count[x]
  • dfs to get answer ans[0]
  • node, parent
  • dfs(child, node)
  • count[node] = sum of count[child] + 1
  • ans[node] = sum of ans[child] + sum of count[child]
  • dfs2 to update ans[x]
  • node, parent
  • ans[child] = ans[node] - count[child] + (N - count[child])
  • dfs2(child, node)
• https://leetcode.com/problems/stream-of-characters/
  • solved with trie
• https://leetcode.com/problems/permutations-ii/
  • dfs (visited, used)
• https://leetcode.com/problems/delete-nodes-and-return-forest/
  • solved recursive way
• https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
  • solved with binary search 3 times
  • find matched value
  • find start (0, lo)
  • find last (lo, N-1)
  • More Efficient version
  • firstGreaterOrEquals
  • start = firstGreaterOrEquals(target)
  • end = firstGreaterOrEquals(target+1)
• https://leetcode.com/problems/n-queens-ii/
  • backtracking
  • cols : col
  • diag1 : row - col (or row - col + n)
  • diag2 : row + col
• https://leetcode.com/problems/n-queens/
  • same way
• https://leetcode.com/problems/unique-binary-search-trees-ii/
  • select root value from values
  • build left & right possible subTree
  • build current tree
• https://leetcode.com/problems/bus-routes/
  • BFS
  • visited-bus
  • visited-station
• https://leetcode.com/problems/unique-binary-search-trees-ii/
  • build
  • for i from List possible
  • set i as a root
  • root.left = build(subList of possible < i)
  • root.right = build(subList of possible > i)
• https://leetcode.com/problems/largest-1-bordered-square/
  • count continuous 1 V(ertically), H(orizontally)
  • k (min value of V[i][j], H[i][j]) to atleast (the sqrt of current max)
  • V[i][j-k+1] >= k && H[i-k+1][j] >= k
• https://leetcode.com/problems/string-without-aaa-or-bbb/
  • A > B
  • B <= A

[kymr]

• https://leetcode.com/problems/next-greater-element-iii/
  • from N-1 to 0, find digit[i] > digit[i-1]
  • if i == 0 then -1
  • from i+1 to N-1, find the smallest digit[j] is greater than digit[i-1]
  • swap (digit[i-1], digit[smallest])
  • swap i to N-1
• https://leetcode.com/problems/add-and-search-word-data-structure-design/
  • solved with Trie
• https://leetcode.com/problems/rotate-function/
  • total, sum
  • for i to N-1
  • total = total - sum + (A[i] * N)
• https://leetcode.com/problems/contain-virus/
  • base
  • Set seen
  • List<Set> regions
  • List<Set> frontiers
  • List perimeters
  • simulate every day
  • init and build base with dfs
  • if no regions found, then break
  • find the most threaten region i based on frontiers.size()
  • ans += perimeters.get(i)
  • for each region
    • if i, then set all cells to -1
    • else, for each cell,
    • if adjacent cell is uncontaminated (0), then change it to 1
• https://leetcode.com/problems/stone-game/
  • Alex always wins.
  • DP[left][right][turn]
  • if turn == 1
  • Math.max(P[left] + helper(left+1, right, 0), P[right] + helper(left, right-1, 0)
  • if turn == 0
  • Math.min(-P[left] + helper(left+1, right, 1), -P[right] + helper(left, right-1, 1)
• https://leetcode.com/problems/ugly-number-iii/
  • count(a, b, c, n) : How many ugly numbers 1 to n?
  • (num / a) + (num / b) + (num / c) - (num / lcm(a, b)) - (num / lcm(b, c)) - (num / lcm(a, c)) + (num / lcm(a, b, c))
  • lcm(a, b) = a * b / gcd(a, b)
  • gcd(a, b)
    • if a == 0, then b
    • else gcd(b % a, a)
  • binary search lo = 1, hi = Integer.MAX_VALUE
  • if count(a, b, c, mid) < n, then lo = mid + 1
  • else hi = mid
• https://leetcode.com/problems/filling-bookcase-shelves/
  • DP[0] = 0;
  • DP[i+1] is the minimum height of shelves that are filled until i-th book
  • for i 0 to N-1
  • for j i-1 to 0 && sum(w, j to i) <= W
    • update DP
• https://leetcode.com/problems/guess-the-word/
  • minimax problem
  • match(str1, str2) returns the count of matched letters.
  • For every guess(picked-word)
  • remove from the list, match(picked-word, word) != guess-result
  • But the problem is
  • the probability of match-result 0 of two randomly picked words is about 80% ((25/26) ^ 6)
  • so we cannot remove word from the list as much as we want
  • So, we should pick the word efficiently to minimize worst-case
  • For every word from the remain list, count the number of match(word, others) == 0
  • pick the word which one is minimum count.
• https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/
  • Traversing from the left most bit to right
  • if A[i] == 0 then flip, or skip
  • It costs a lot if we flip K bits every time we flip
  • So, we need more efficient way.
  • isFlipped[i] : is i-th bit flipped?
  • flipped : Is current bit flipped?
  • for (i >= K) flipped ^= isFlipped[i-K], because it is different to previous one.
• https://leetcode.com/problems/longest-mountain-in-array/
  • tracking up & down
  • init if it is not possible mountain or the start of mountain
  • update longest
• https://leetcode.com/problems/count-binary-substrings/
  • solved with zeroOne[2] array
  • the other approach is
  • increase cur if (s.charAt[i-1] s.charAt[i])
  • result += Math.min(pre, cur)
• https://leetcode.com/problems/binary-tree-coloring-game/
  • There are 3 possible choices that y can choose
  • nodeX.left
  • nodeX.right
  • nodeX.parent
• https://leetcode.com/problems/queens-that-can-attack-the-king/
  • for each 8 directions, find the first queen met.
• https://leetcode.com/problems/find-in-mountain-array/
  • find peak in the mountain array
  • binary-search
  • mid < mid+1 => asc => lo = peak = mid + 1
  • mid > mid+1 => desc => hi = mid
  • find target 0 to peak (asc)
  • if not found, find target peak to N-1 (desc)
• https://leetcode.com/problems/find-in-mountain-array/
  • Find peak (mid vs mid+1)
  • Find the target value from 0 to peak (ASC)
  • Find the target value from peak to N-1 (DESC)
• https://leetcode.com/problems/4sum-ii/
  • sum-count map (A, B)
  • get count -(C, D) of sum-count map

[kymr]

• https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/
  • boolean dfs(node, voyage)
• https://leetcode.com/problems/non-overlapping-intervals/
  • Sort the array
  • Greedy. compare with last (initialized with intervals[0][1])
  • if overlapped
  • not overlapped, remove the one which interval[1] is greater
• https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/
  • solved with stack
• https://leetcode.com/problems/decrease-elements-to-make-array-zigzag/
  • for i to N-1
  • left is nums[i-1] or 1001
  • right is nums[i+1] or 1001
  • res[i%2] += Math.max(0, nums[i] - Math.min(left, right) + 1);
• https://leetcode.com/problems/trapping-rain-water/
  • 2 pointers
  • left = 0, right = N -1, H = 0, result = 0
  • while (left < right)
  • int L = height[left], R = height[right]
  • if L <= R
    • result += Math.max(0, H - L), left++
  • else
    • result += Math.max(0, H - R), right--
  • H = Math.max(H, Math.min(L , R))
• [Contest] https://leetcode.com/contest/weekly-contest-163/problems/shift-2d-grid/
  • Shifting using Queue
• [Contest] https://leetcode.com/contest/weekly-contest-163/problems/find-elements-in-a-contaminated-binary-tree/
  • Recovering Tree & build Set
• [Contest] https://leetcode.com/contest/weekly-contest-163/problems/greatest-sum-divisible-by-three/
  • Sort
  • Sum & Map<[0, 1, 2], List>
  • k % 3 == 0
  • k % 3 == 1
  • k % 3 == 2
• [Contest] https://leetcode.com/contest/weekly-contest-163/problems/minimum-moves-to-move-a-box-to-their-target-location/
  • 2 BFS
• [Contest] https://leetcode.com/contest/biweekly-contest-13/problems/synonymous-sentences/
  • Merge Synonyms & Sort
  • DFS
• [Contest] https://leetcode.com/contest/biweekly-contest-13/problems/smallest-common-region/
  • Map<String, Integer> regionMap
  • traverse region 1 & build order
  • tarverse region 2 & build order
  • compare and find first
• https://leetcode.com/problems/remove-boxes/
  • not self-contained problem => make it self-contained problem
  • T(i, j, k)
  • the maximum points that I can get from (i, j)
  • k is the count of boxes those are same color with boxes[i]
  • Initiation
  • T(0, N-1, 0)
  • Terminal
  • T(i, i, k) : (k + 1) * (k + 1)
  • T(i, i-1, k) : 0
  • 2 cases
  • move box i
    • (k + 1) * (k + 1) + T(i + 1, j, 0)
  • leave it until next box m which is same color with i
    • T(i + 1, m - 1, 0) + T(m, j, k + 1)
    • for m is (i + 1, j)
  • Memoization for (i, j, k)
• https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
  • if root == null || root is p or q
  • left && right
  • left != null && right != null
  • left or right

[kymr]

• https://leetcode.com/problems/valid-permutations-for-di-sequence/
  • dp[i][j] = i th element is jth smallest number at left digits
  • dp[0][i] = 1
  • for i 0..N-1
  • if s.charAt(i) == ‘I’
    • for j 0 to N-i-1
    • dp[i+1][j] = cur = (cur + dp[i][j]) % mod
  • else (‘D’)
    • for j N-i-1 to 0
    • dp[i+1][j] = cur = (cur + dp[i][j+1]) % mod
• https://leetcode.com/problems/boats-to-save-people/
  • two pointers

[kymr]

[kymr]

• https://leetcode.com/problems/dinner-plate-stacks/
• https://leetcode.com/problems/custom-sort-string/
• https://leetcode.com/problems/image-overlap/
  • using i, j delta
  • for A & B
  • if val[i][j] is 1, then convert i, j to integer value
  • for i : A, for j : B
  • countMap.put(i - j, +1);
• https://leetcode.com/problems/maximum-sum-circular-subarray/
  • maximum subarray & minimum subarray
• https://leetcode.com/contest/weekly-contest-169/problems/verbal-arithmetic-puzzle/
  • TODO
• TODO
  • Remind leetcode contest result

[kymr]

• https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/
  • bit mask