- https://www.geeksforgeeks.org/must-do-coding-questions-for-companies-like-amazon-microsoft-adobe/#arrays
- https://github.com/xiaoylu/leetcode_category
- EG
- 1st cycle
- [1, 6(i), 3, 4, 3, 5](just_loop, no_chg) -> 1, 5, 3, 4, 3, 5
- 1, 6, 3(i), 4, 3, 5 -> 1, 5, 4, 4, 3, 5
- 1, 6, 3, 4(i), 3, 5 -> 1, 4, 4, 3, 3, 5
- 1, 6, 3, 4, 3(i), 5 -> 1, 4, 4, 3, 4, 5
- 2nd cycle
- [1, 4(i), 4, 3, 4, 5](just_loop, no_chg) -> 1, 4, 4, 3, 4, 5
- 1, 4, 4(i), 3, 4, 5 -> 1, 4, 4, 3, 4, 5
- 1, 4, 4, 3(i), 4, 5 -> 1, 4, 4, 4, 4, 5
- 1, 4, 4, 3, 4(i), 5 -> 1, 4, 4, 4, 4, 5
- 3rd cycle
- [1, 4(i), 4(i), 4(i), 4(i), 5](i_exhaust, no more)
- SUMMA
- out_loop (many cycles)
- tmp = arr (clone)
- in_loop (1 cycle)
- big 2 side, down; op=true;
- small 2 side, up; op=true;
- if op == false, break
- end_in_loop, arr = tmp (revert);
- https://leetcode.com/problems/array-transformation
- https://www.programmersought.com/article/74733416873
- EG
- SUMMA
- intersection: (1_ele_in_another)
- unique: ([...set])
- https://leetcode.com/problems/intersection-of-two-arrays
- EG
- SUMMA
- unique: ([...set], [...set])
- intersection: (1_ele_in_another)
- https://leetcode.com/problems/intersection-of-two-arrays
- EG
- SUMMA
- unique: (map_ns1[ns1])
- intersection: map_ns1[ns2] -> map_ns2[ns2]
- https://leetcode.com/problems/intersection-of-two-arrays
- EG
- 1, 2, 3, pure (1 loop, 2_same_kind_var track pureness)
- 3, 2, 1, prue (..)
- 2, 2, 2, pure (..)
- [1, 2, -100, 100], !pure (..)
- SUMMA
- loop eles
- if asc + desc set, !pure (1 loop, 2_same_kind_var track pureness)
- if asc set, pure (..)
- if desc set, pure (..)
- if asc + desc !set, !touch, equal (..)
- https://leetcode.com/problems/monotonic-array
slide_window_avoid_rest_ops; res == 1; i < a.len - len VS a[i+len]; sorted, a[i] == start_val, a[i+len] == end_val, start_val == end_val
- EG
- [1, 2, 2, 6, 6, 6, 6, 7, 10], len = 9, quarter_len = 9/4 -> floor(2.25) = 2;
- ceil(2.25) = 3, 3*4_quarter = 12_too_big
- SUMMA
- len = a.len / 4 (floor)
- single_loop(i=0; i < a.len - len; ..); (i < a.len - len VS a[i+len])
- if a[i] == a[i + len], re a[i]; (sorted, a[i] == start_val, a[i+len] == end_val, start_val == end_val)
- https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array
slide_window_avoid_rest_ops; max_in_slide_win; i_diff_spd_pt_same_start; j_diff_spd_pt_same_end; sum == curr_win_size_in_val, plus ns[j] == extend_win_right; end-start, affect curr_win_size_in_len; sum == curr_win_size_in_val, minus ns[j] == shrink_win_left;
- EG
- [2, 3, 4, 1, 5], k = 3; e.g. [2, 3, 4] or [2, 4, 1] or [4, 1, 5]; max = 4+1+5=10
- SUMMA
- i_diff_spd_pt_same_start
- j_diff_spd_pt_same_end
- outloop (j < len)
- sum = sum + ns[j] (sum == curr_win_size_in_val, plus ns[j] == extend_win_right)
- if end - start = k-1 (end-start, affect curr_win_size_in_len)
- ma = ma(ma, sum) (update_max)
- sum = sum - ns[i] (sum == curr_win_size_in_val, minus ns[j] == shrink_win_left)
- end_if, ++j (extend_win_right)
- re max / k
- https://leetcode.com/problems/maximum-average-subarray-i
- EG
- SUMMA
- [4, 3, 2, 1] -> [1, 2, 3, 4] (greedy, sort)
- max = min(1, 2) + min(3, 4) (group_2)
- https://leetcode.com/problems/array-partition-i/
[2, 5, 3, 1, 1] (missing 4); ind = ele - 1; [2-1(ind), 5-1(ind), 3-1(ind), 1-1(ind), 1-1(ind)]; [-2, -5, -3, x, -1]; ele = ind + 1; ele === ind; mark_num
- EG
- SUMMA
- loop eles
- if pure - or +, ind info lost; num val has to stay; can mark -
- ind needs +
- because 1 -> n, so index - 1
- access ele; meet again or brand new ele
- make it always -
- if sth not mark, someone else has dup and they occupy the position.
- https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array
missing_1_num; [3, 0, 1] -> [0, 1, 3] (2 missing) -> [0, 1, 2, 3] (full); diff = 0, 1, 2, 3 - 0, 1, 3
- EG
- SUMMA
- ns has zero
- ns = [3, 0, 1] -> [0, 1, 3] -> [0, 1, 3] (missing 2)
- full: [0, 1, 2, 3]
- diff = [0, 1, 2, 3] - [0, 1, 3]
- https://leetcode.com/problems/missing-number
[2, 3, 1, 1, 1] -> [1, 1, 1, 2, 3]; vote_algo; same_ele_vote, diff_ele_vote_cancel, vote_exhaust_new_major
- EG
- SUMMA
- vote_algo
- major = ns[0]; counter = 1; (1st_ele major)
- loop ele (i=1)
- if c === 0; major = n[i], c=1 (vote_exhaust_new_major)
- if major === ns[i]; ++c (same_ele_vote)
- else --c (diff_ele_vote_cancel)
- https://leetcode.com/problems/majority-element
- EG
- SUMMA
- method 1:
- prepare on the fly (hash); flow_down (priority queue like)
- method 2:
- prepare before (hash); priority queue (find insert posi, shift left); m1 = -max (num vs num)
- https://leetcode.com/problems/third-maximum-number
- EG
- SUMMA
- method 1:
- rem posi; flow_down (priority queue like)
- method 2:
- rem posi; priority queue
- https://leetcode.com/submissions/detail/494400148/
- https://leetcode.com/problems/largest-number-at-least-twice-of-others
- EG
- SUMMA
-
- method 1:
- rem posi; flow_down (priority queue like)
- method 2:
- rem posi; priority queue
- https://leetcode.com/submissions/detail/494662342/
- https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array
- EG
- SUMMA
- flowdown or priority queue; +, +, + VS +max, -, -
- https://leetcode.com/submissions/detail/494667667/
- https://leetcode.com/problems/maximum-product-of-three-numbers
top 5 subject scores for each student; [[1, 91], [1, 92], [2, 81], [1, 60]] -> [[1, 91], [1, 92], [1, 60], [2, 81]]; prepare before (hash) + flow_down
- EG
- SUMMA
- prepare before (hash) + flow_down
- https://www.cnblogs.com/cnoodle/p/13722300.html
- https://leetcode.com/problems/high-five
- EG
- SUMMA
- priority queue (find insert posi, shift_left)
- https://leetcode.com/submissions/detail/494223381/
- https://leetcode.com/problems/kth-largest-element-in-an-array
- EG
- SUMMA
- i=0
- [0(i_no_i-1), 1, 2, 3, 4], 5pt
- i=1
- [1, -100(i_look_back, drop, out_of_trend_low), 2, 3, 4], 5pt; (left_before_edge)
- i=2
- [1, 2, -100(i, drop, out_of_trend_low), 3, 4], 5pt; (too_low; i-1, i, i+1)
- i=3
- [1, 2, 100(out_of_trend_high), 3(i, drop), 4], 5pt; (too high; i-2, i)
- .....
- i=len-2
- [1, 2, 3, -100(i, drop, out_of_trend_high), 4], 5pt; (too low; i-1, i, i+1)
- i=len-1
- [1, 2, 3, 4, -100(i, drop, i_last)], 5pt; (right_edge)
- https://leetcode.com/problems/non-decreasing-array
- EG
- SUMMA
- INVERSE_QUESTION; most re_fail, else re_true
- loop(i=0; i<=len-2; ..) (normal_scan_loop, 2_ele_diag, upto_2nd_last)
- loop(j=0; j<=len-2; ..) (normal_scan_loop, 2_ele_diag, upto_2nd_last)
- if ma[i][j] !== ma[i+1][j+1] re_fail (INVERSE_QUESTION, most re_fail)
- https://leetcode.com/problems/toeplitz-matrix
- EG
- 10 -> B or 11 -> B; 0 -> A; 0_end
- [0(end)], t
- [0, 0(end)], t
- [1, 0(end)], f
- [0, 0, 0(end)], t; (0 + 0_end, because 1 uses 1st 0)
- [0, 1, 0(end)], f; (odd_sequence_1s)
- [1, 0, 0(end)], t; (0 + 0_end)
- [1, 1, 0(end)], t; (even_seq_1s)
- [0, 0, 0, 0(end)], t; (0 + 0_end)
- [0, 0, 1, 0(end)], f; (odd_seq_1s)
- [0, 1, 0, 0(end)], t; (0 + 0_end)
- [1, 0, 0, 0(end)], t; (0 + 0_end)
- [0, 1, 1, 0(end)], t; (even_seq_1s)
- SUMMA
- loop(i=len-2; ns[i]!==0 && i>=0; --i); ignore_ending_0
- backward; count_seq_1s; odd_seq_1s false; even_seq_1s true;
- https://leetcode.com/problems/1-bit-and-2-bit-characters
- EG
- SUMMA
- end_write, end_m_read, end_n_read (1_write, 2_reads)
- while(n>=0) (scan_from_right)
- n1[end_w--] = n1[end_m_r] > n2[end_n_r] ? n1[end_m_r--] (1_write, 2_reads)
- n1[end_w--] = n1[end_m_r] <= n2[end_n_r] ? n2[end_n_r--] (1_write, 2_reads)
- https://leetcode.com/problems/merge-sorted-array
- EG
- SUMMA
- backward loop eles
- if ds[i] === IGNORE_CARRY (9); ds[i] = 0; con_loop
- if ds[i] === ADD_ONE (0, 1, 2..8); ds[i]++; return
- end_loop, prepend 1; e.g. 999, con_loop
- https://leetcode.com/problems/plus-one
- EG
- SUMMA
- [4(i), 3, 2, 1] -> [3(i), 3, 2, 1]; curr_ele == 4, replace_with_3
- [3, 3(i), 2, 1] -> [3, 2(i), 2, 1]; curr_ele == 3, replace_with_2
- ..
- [3, 2, 2, 1(i)] -> [3, 2, 2, -1(i)]; last_ele = -1
- single_loop(i=0; i<len..)
- a[i] = ma(...a.slice(i+1))
- end_loop a[a.len-1] = -1
- https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side
- EG
- posi = [2, 2, 2, 3, 3]; posi 1 == 0 chip; posi 2 == 3 chips; posi 3 == 2 chips
- odd_to_odd, even_to_even, cost 0; odd_to_even, even_to_odd, cost 1
- SUMMA
- loop eles
- if odd, ++odd
- if even, ++even
- end_loop;
- if odd == arr.len, re 0; (odd_to_odd, cost 0)
- if even == arr.len, re 0; (even_to_even, cost 0)
- else re min(odd, even) (e.g. [2, 2, 2, 3, 3], 3 less moves)
- https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position
- EG
- SUMMA
- loop_rows (2D)
- loop_cols (2D)
- start_i, end_j
- if(ma[k][i] == ma[k][j]), when_same_flip_both
- if(ma[k][i] != ma[k][j]), when_diff_do_nothing
- https://leetcode.com/problems/flipping-an-image
- EG 1 2 3 4 5 6 => 1 4 2 5 3 6
- (0, 0) -> (0, 0)
- (0, 1) -> (1, 0)
- (0, 2) -> (2, 0)
- ...
- SUMMA
- build res matrix
- loop_row
- loop_col
- res[j][i] = ns[i][j]
- https://leetcode.com/problems/transpose-matrix
outloop(row_1D_arr_slot_xxx); inloop(col_1D_arr_slot_xxx); row_1D_arr_slot_xxx X col_1D_arr_slot_xxx -> 2D
outloop(row_1D_arr_slot_acc); inloop(col_1D_arr_slot_acc); row_1D_arr_slot_acc x col_1D_arr_slot_acc -> 2D
- EG
- method 1: do_row, do_col; do_row, do_col
- ind: [[0_row, 1_col], [1_row, 1_col]]
- 0 0 -> 1 1 -> 1 2 ==> 1 2 -> 1 3
- 0 0 -> 0 0 -> 0 1 ==> 1 2 -> 1 3
- method 2: do_row, do_row; do_col, do_col
- ind: [0_row, 1_row]
- 0 0 -> 1 1 -> 1 1
- 0 0 -> 0 0 -> 1 1
- ind: [1_col, 1_col]
- 0 0 -> 0 1 -> 0 2
- 0 0 -> 0 1 -> 0 2
- merge_2
- do_row, do_col; do_row, do_col ===> do_row, do_row; do_col, do_col
- SUMMA
- single_loop(income_ind_arr)
- row_1D_arr_slot_acc
- col_1D_arr_slot_acc
- outloop(row_1D_arr_slot_acc)
- inloop(col_1D_slot_acc)
- if (row_1D_arr_slot_acc[i] + col_1D_slot_acc[j]) % 2 == 0, ++counter
- https://leetcode.com/problems/cells-with-odd-values-in-a-matrix
outloop(row_1D_arr_slot_max, move_down); inloop(col_1D_arr_slot_min, move_right); row_1D_arr_slot_max x col_1D_arr_slot_min -> 2D
- EG matrix: 1, 2, 3, 4 5, 6, 7, 8 9, 10, 11, 12
- outloop(row_1D_arr_slot_max, move_down)
- inloop(col_1D_arr_slot_min, move_right)
- row_1D_arr_max = [1, 2, 3, 4] -> [5, 6, 7, 8] -> [9, 10, 11, 12]
- col_1D_arr_min = [1, 5, 9] -> [1, 5, 9] -> [1, 5, 9] -> [1, 5, 9]
- 1D x 1D = outloop(row_1D_arr_slot_max) x inloop(col_1D_arr_slot_min)
- res = [9], cross_over
- SUMMA
- outloop(row_1D_arr_slot_max, move_down)
- inloop(col_1D_arr_slot_min, move_right)
- row_1D_arr_max[i] = ma(matrix[i][j], ma[i]) (slot_not_finish)
- col_1D_arr_min[j] = mi(matrix[i][j], mi[j]) (slot_finish)
- outloop(row_1D_arr_slot_max)
- inloop(col_1D_arr_slot_min)
- if ma[i] == mi[j], arr.push (row_1D_arr_slot_max x col_1D_arr_slot_min -> 2D)
- https://leetcode.com/problems/lucky-numbers-in-a-matrix
sorted_desc_matrix, row_desc, col_desc; top_left_big, bottom_right_small; row_ind_go_up,col_above_same_or_behind
sorted_desc_matrix, row_desc, col_desc; top_left_big, bottom_right_small; row_ind_go_up,col_above_same_or_behind
- EG
- SUMMA
- ! + + + + + +
- ! + + + - - -
- ! + + - - - -
- ! + - - - - -
- ! - - - - - -
- sorted_desc_matrix, row_desc, col_desc
- top_left_big, bottom_right_small
- ! + + + + + +
- ! + + + - - -
- ! + + - - - -
- ! + -(col_above_same_or_behind) - - - -
- ! -(col) - - - - - (row_ind_go_up)
- https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix
-
EG
-
SUMMA
-
2D -> 1D -> 2D; a_old[i_total / old_w][i_total % old_w] -> a_mid[i_total = i_total = r * width + c] -> a_new[i_total / new_w][i_total % new_w]
-
old_w * old_h === new_w * new_h;
-
loop(i_total=0; i < old_w * old_h; ..); 2D -> 1D; a_old[i_total / old_w][i_total % old_w] -> a_mid[i_total = r * width + c]
-
a_new[i_total / new_w][] = a_old[i_total / old_w][i_total % old_w]
- EG
- SUMMA
- 2D -> 1D; loop(i=0; i<m*n; ..); a_mid[i_total] = a_old[i_total / old_w][i_total % old_w];
- shift; loop(i=0; i<m*n; ..); a_new_1D[(i_total + k) % len] = a_mid[i_total];
- 1D -> 2D; in_loop, out_loop; a_new_2D[i][j] = a_new_1D[i * width + j];
- https://leetcode.com/problems/shift-2d-grid
- EG
- SUMMA
- [ r:[0, 1, 2], [3, 4, 5], [6, 7, 8], c:[0, 3, 6], [1, 4, 7], diag[2, 5, 8], [0, 4, 8], [2, 4, 6] ] (3_win)
- loop input_arr (fill_tic_tac)
- a_mid[ c * width + r ] = (i_A_OR_B % 2) + 1; (2D -> 1D; a_old[r][c] -> a_mid[ c * width + r])
- loop win
- if a_mid[ win[i][0] ] == a_mid[ win[i][1] ] == a_mid[ win[i][2] ] && not_eq_zero (3_win)
- either re 'A' or 'B'
- end_loop; input_arr.len === 9 re 'DRAW'; else 'PENDING'
- https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game
- EG
- SUMMA
- loop !eof(when small) && total < out_req_n_char (when small)
- count(full || mod_left) = read_4_char
- count = mi( count(full || mod_left), when_small; out_req_left, when_small )
- copy char
- https://evelynn.gitbooks.io/google-interview/content/read_n_characters_given_read4.html
- EG
- SUMMA
- loop chars
- arr.splice(i, 1_delete_count), remove_in_place
- splice; (len_reduce, --i && ++i_back_to_top)
- https://www.geeksforgeeks.org/program-remove-vowels-string
- EG
- SUMMA
- loop eles
- i=1, i<a.len
- if a[i] == a[i-1], a.splice(i-1, 1_delete_count); (len_reduce, --i && ++i_back_to_top)
- https://www.geeksforgeeks.org/program-remove-vowels-string
- EG
- SUMMA
- loop chars
- arr.splice(ind, 0_delete_count, "["), insert at ind front
- i = i+2; 123.(i)41.xxxx -> 123[.4(i)1
- arr.splice(ind, 0_delete_count, "]"), insert at ind front
- https://leetcode.com/problems/defanging-an-ip-address
what_diff_type_pt? (1) i_slow_pt_diff, j_fast_pt_diff(LOOK_BACK); (2) i_same_spd_pt_diff, j_same_spd_pt_diff(i_start + len); (3) i_same_spd_pt_diff, j_same_spd_pt_diff(tracking_var); (4) i_diff_spd_pt_same, j_diff_spd_pt_same(????);
- EG
- abc VS ab; diff_len, A_cannot_swap
- aab VS aab; same_and_dup, A_can_swap "aa"
- ab VS ba; i_same_spd_pt_diff, j_same_spd_pt_diff(tracking_var)
- SUMMA
- if diff_len, A_cannot_swap, re f
- if same_and_dup, A_can_swap, re t
- else i_same_spd_pt_diff, j_same_spd_pt_diff(tracking_var);
- e.g. ab VS ba; var1 = [a, b], var2 = [b, a]
- if var1[0] == var2[1] && var1[1] == var2[0]
- https://leetcode.com/problems/buddy-strings
-
EG
-
["flower","flow","flight"]; flower as prefix; flower vs flow -> flow(er); flow vs flight -> fl(ow);
-
SUMMA
-
arr[0] as prefix (global)
-
out_loop (i=1, i<len) (outloop_each_word)
-
in_loop(non_found_prefix_loop)
-
(prefix_reduce_1_char; compare_with_input_word)
-
prefix === '', re ''
-
end_loop, prefix
-
https://www.geeksforgeeks.org/longest-common-prefix-using-character-by-character-matching (vertical w by w matching char)
["cool", "lock", "cook"]; cook as common; cool vs lock -> co (ol); co vs cook -> co(); if_common, rm from input_word; if_non_common, rm from common
- EG
- SUMMA
- arr[0] as common (global)
- out_loop (i=1, i<len) (outloop_each_word)
- in_loop(loop_each_char_in_common)
- (1)
- vertical compare
- common: aac; first_a stay; for next input_word (global)
- input: abc; first_a gone; next_common_char won't check again
- (2)
- vertical compare
- common: xy; first_x gone; next input_word won't use (global)
- input: abc; first_a stay; next_common_char may hit
- in_summary; if_common, rm from input_word; if_non_common, rm from common
- https://leetcode.com/problems/find-common-characters
- EG
- [1, 1, 4, 2, 1, 3] -> sort -> [1, 1, 1, 2, 3, 4]; vertical_compare; not_equal_res_inc
- SUMMA
- orig_arr;
- sort_arr;
- loop ele
- vertical_compare; not_equal_res_inc
- https://leetcode.com/problems/height-checker
IVIV(roman) -> IV(s, s+1) -> compare(sb 1 group || b 1 group); i(start), i(start+1), j(x, end), j(x, end-1); i move right; access_hash
- EG
- IVIV -> (sb)(sb) -> (IV)(IV)
- VIVI -> (b)(sb)(b, end) -> (V)(IV)(I)
- SUMMA => sb 1 group, b 1 group
- build HASH (from Q, has all combo)
- loop chars
- curr = h[i], next = h[i+1] (LOOK_AHEAD, i_stay)
- if curr >= next, b 1 group
- else next < curr, sb 1 group, fast_forward
- else the_end_char
- https://leetcode.com/problems/roman-to-integer
IVIV(roman) -> IV(s, s+1) -> in_hash(sb 1 group || b 1 group); i(start), i(start+1), j(x, end), j(x, end-1); i move right; access_hash
- EG
- IVIV -> (in_h)(in_h) -> (IV)(IV)
- VIVI -> (in_h)(in_h)(in_h) -> (V)(IV)(I)
- SUMMA => h[ s[i] + s[i+1] ] (LOOK_AHEAD, i_stay)
- build HASH (from Q, has all combo)
- loop chars
- if h[ s[i] + s[i+1] ], fast_forward
- else 1_char_acc
- https://leetcode.com/problems/roman-to-integer
- EG
- a1: [3, 4, 1, 1, 2, 2]
- a2: [1, 2]
- h: {3:1, 4:1, 1:2, 2:2} (build_knowledge)
- out: [1, 1, 2, 2, 3, 4]
- SUMMA
- ..
- ..
- loop 0->1000 (e.g. loop 1 -> 1000 or loop a -> z, natural_bottom_up)
- use all freq
- res.push(build_from_ground)
- https://leetcode.com/problems/relative-sort-array
[1,1,4,2,1,3] -> how_many_move -> [1, 1, 1, 2, 3, 4]; natural_bottom_up + consume_hash === input_arr_len
- EG
- [1,1,4,2,1,3] -> how_many_move -> [1, 1, 1, 2, 3, 4] (sort)
- SUMMA
- hash 0, 1, 2, 3 -> 100 (natural_bottom_up)
- out_loop 1 -> 100 (natural_bottom_up)
- input_arr_ind = 0 (global)
- i === height
- in_loop( (hash[i]--) > 0); (natural_bottom_up + consume_hash === input_arr_len)
- input_arr[ input_arr_ind ] !== i_height; res++; e.g. input_arr[1] may == input_arr[100], beause dup
- https://leetcode.com/problems/height-checker
- EG
- ns = [3,4,-1,1], missing == 2
- ns = [-1], missing == 1
- SUMMA
- single_loop (hash_prepare)
- single_loop (i=1; i<=max) (max, natural_bottom_up)
- if hash[ns[i]], con; else re (fill_gap)
- https://leetcode.com/problems/first-missing-positive
- EG
- ns = [1, 2, 3, 4, 6], no_gap_until_5, missing == 5
- SUMMA
- single_loop (hash_prepare)
- single_loop (i=1; i<=len) (len, natural_bottom_up)
- if hash[ns[i]], con; else re (fill_gap)
- https://leetcode.com/problems/first-missing-positive/discuss/927112/Three-JS-Solutions
- EG
- ns = [1, 2, 3, 4, 6], no_gap_until_5, missing == 5
- SUMMA
- set, sort, filter (positive_uniq)
- single_loop (ele); j == ns[i]_no_gap, ++j; (find_1st_gap_in_input)
- https://leetcode.com/problems/first-missing-positive/discuss/927112/Three-JS-Solutions
- EG
- [1,0,0,0,0,0,1], k = 2 -> [1,0,0(1),0,0(1),0,1]
- SUMMA
- if fb[i-1] = 1, skip (LOOK_BACK)
- if fb[i] = 1, skip (LOOK_SELF)
- if fb[i+1] = 1, skip (LOOK_AHEAD)
- after_all, ++counter
- end_loop, counter >= k?
- https://leetcode.com/problems/can-place-flowers
- EG
- ab___cd__efg__; b_, d_, g_ means 3 word_segment
- SUMMA => letter space == word_segment
- loop chars
- i-1, i(LOOK_BACK, i_move); if(s[i-1] == ' ', s[i] == letter), word_segment++
- https://leetcode.com/problems/number-of-segments-in-a-string
- EG
- SUMMA
- copy_arr
- sort_arr
- LOOK_BACK(same; i=1)
- loop_sort_arr;
- LOOK_BACK(same; i=1), when_same_rank_stay, when_diff_rank_inc;
- loop_orig_arr, assign_rank
- https://leetcode.com/problems/number-of-segments-in-a-string
a2 in a1; a1 follows a2 order; res build_from_ground_rearrange(i_hash_fill_res + j_natural_bottom_up_fill_res VS res_ind )
- EG
- a1: [3, 4, 1, 1, 2, 2]
- a2: [1, 2]
- h_a1: {3:1, 4:1, 1:2, 2:2}
- out: [1, 1, 2, 2, 3, 4]
- SUMMA
- h_a1
- loop a2 (a1 follows a2 order)
- use h_a1 to print freq (i_hash_fill_res)
- res.push
- end_loop, reset freq
- loop 0->1000 (e.g. loop 1 -> 1000 or loop a -> z; j_natural_bottom_up_fill_res)
- use all freq
- res.push
- https://leetcode.com/problems/relative-sort-array
build_from_ground_rearrange(i_big_fill_res, i_small_fill_res VS res_ind); [-4(i_start), -3, 1, 2(j_big)] -> [1, 4, 9, 16];
- EG
- sort + -; big head?, big tail?
- why push big -> small?
- if small to big, e.g. [-4(i_small), -3, 1, 2(j_big)] -> [2^2, 1^2, -3^2, ..] (wrong)
- push big -> small
- [-4(i_small), -3, 1, 2(j_big)] -> [1, 4, 9, 16];
- SUMMA
- res = [], ind = j_end;
- i_small, j_big
- loop(i <= j)
- if ns[i]^2 > ns[j]^2, res[ind--](can be arr / hash) = ns[i]^2; (i_big_fill_res; res_ind)
- if ns[i]^2 <= ns[j]^2, res[ind--](can be arr / hash) = ns[j]^2 (i_small_fill_res; res_ind)
- https://leetcode.com/problems/squares-of-a-sorted-array
- EG
- SUMMA
- loop chars
- move along, keep replacing, move back 2 chars
- https://leetcode.com/problems/decrypt-string-from-alphabet-to-integer-mapping
- EG
- ..
- SUMMA => feature represent entire (letter space == word_segment)
- ..
- ..
- https://leetcode.com/problems/number-of-segments-in-a-string
- EG
- ws = ["cat", "dog", "xxxx"]; chars = "atach"
- SUMMA
- build_hash_freq
- loop ws
- loop ws[i] (char)
- if hash_freq[n] === undef || --hash_freq[n] < 0, skip this
- https://leetcode.com/problems/find-words-that-can-be-formed-by-characters
- EG
- SUMMA
- hash_freq
- loop chars (lookup_in_order)
- meet frequency 1
- https://leetcode.com/problems/first-unique-character-in-a-string
- EG
- SUMMA
- hash_freq
- e.g. a:3 (even), can use all
- e.g. b:2 (odd), can use 3-1=2; later add 1
- ba a ab
- https://leetcode.com/problems/longest-palindrome
- EG
- SUMMA
- loop eles
- if h[n] !== undef, h[n] = 1;
- else delete h[n]
- end_loop; max(... Obj.keys(hash) )
- https://leetcode.com/problems/largest-unique-number/
[[1,2],[2,1],[3,4],[5,6]] -> [[1,2],[1, 2],[3,4],[5,6]] 1 pair; hash[ str(complex_ele) ]; dp(same_var_curr) = dp(same_var_prev) + x
- EG
- n=1, a -> 0
- n=2, aa -> a(a) -> 1 pair (0_dp + 1_last_few_num)
- n=3, aaa -> a(aa) -> 3 pairs (1_dp + 2_last_few_num)
- n=4, aaaa -> a(aaa) -> 6 pairs (3 + 3)
- n=5, aaaaa -> a(aaaa) -> 10 pairs (6 + 4)
- so dp[n] = dp[n-1] + (n-1) ==> dp(same_var_curr) = dp(same_var_prev) + (n-1)
- SUMMA
- e.g. [[1,2],[2,1],[3,4],[5,6]]
- loop ele
- hash[str(ele)] (stringify_for_complex_ele)
- if hash[n] > 1, use dp(same_var_curr) = dp(same_var_prev) + (n-1)
- https://leetcode.com/problems/number-of-equivalent-domino-pairs
prebuild hash_init_posi / build hash_init_posi along (met / !met) / update hash_init_posi along (met / !met) / build hash_init_posi along (met_the_other / !met_the_other)
- EG
- keyboard: abcdefghijklmnopqrstuvwxyz, word: cba, that is 1 keyboard position (a-z)
- keyboard: pqrstuvwxyzabcdefghijklmno, word: pom, that is another keyboard position (p-o)
- SUMMA
- prebuild hash posi
- loop chars (e.g. cba)
- LOOK_BACK(i=1); dist = h[i] - h[i-1]; res = res + dist
- https://codedestine.com/single-row-keyboard-string-problem
- EG
- SUMMA
- loop chars;
- if met, dist = i - hn - 1;
- if !met, (build hash_init_posi along)
- https://leetcode.com/problems/largest-substring-between-two-equal-characters
- EG
- SUMMA
- loop eles
- if met; if i - h[n] <= k, re t; else h[n] = update_posi (update hash_init_posi along)
- if !met; h[n] = init_posi; (build hash_init_posi along)
- https://leetcode.com/problems/contains-duplicate-ii
[1,2,1,2,1,3,3,2]; {1:3, 2:3, 3:2}; 1 and 2 same max_freq, but 1 is shorter dist; (1) one pass; hash_obj: {freq, distance}; sudden_meet_condi(freq > max_freq || freq == max_freq), update_freq, update_distance
- EG
- SUMMA
- loop eles (one pass)
- hash_obj: {freq, distance}
- sudden_meet_condi(freq > max_freq || freq == max_freq), update_freq, update_distance;
- https://leetcode.com/problems/degree-of-an-array
- EG
- SUMMA
- 1st_tracking_var: w0_ind = -1
- 2nd_tracking_var: w1_ind = -1
- loop eles
- if(item === w0), w0_ind = i
- if(item === w1), w1_ind = i
- if(w0_ind >= 0 && w0_ind >= 0), minD = mi(minD, abs(w0_ind - w1_ind))
- why abs(w0_ind - w1_ind) min?
- https://leetcode.com/problems/shortest-word-distance/
- https://tenderleo.gitbooks.io/leetcode-solutions-/content/GoogleEasy/243.html
- EG
- SUMMA
- hash (no order)
- loop (res.len < s.len)
- sort_hash
- hash_key_arr -> ascending -> copy new sort_hash
- rev_sort_hash
- hash_key_arr -> descending -> copy new rev_sort_hash
- repeat
- https://leetcode.com/problems/increasing-decreasing-string
[1, 2, 11, 12]_num -> [1, 2, 2, 3]_digi_sum_prepare_hash -> [1, 2, 2, 3]_group_sum; nums -> digi_sum_prepare_hash -> group_sum
- EG
- SUMMA
- nums -> digi_sum_prepare_hash -> group_sum
- https://leetcode.com/problems/count-largest-group
- EG
- SUMMA
- loop chars
- indexOf === lastIndexOf, only_1_no_repeat
- https://leetcode.com/problems/first-unique-character-in-a-string
- EG
- SUMMA
- loop mail_arr
- mail, split('@'), split('+'), replace dot;
- set.add (unique), set.size
- https://leetcode.com/problems/unique-email-addresses
- EG
- _abc_d,e,f_g_ -> _abc_d_e_f_g_(maintain segment) -> abc_d_e_f_g(trim_head_tail, split(/+s/)) -> [abc, d, e, f, g]
- SUMMA
- , -> _ (maintain segment)
- trim_head_tail, split(/+s/)
- build_hash, to freq
- https://leetcode.com/problems/most-common-word/
- EG
- SUMMA
- set.add(ele), set.size
- https://leetcode.com/problems/unique-morse-code-words
- EG
- SUMMA
- loop eles (orig_arr)
- if orig_arr.includes(ele + 1); ++count; (loop_each_ele, mod_to_use)
- https://leetcode.com/problems/counting-elements
- https://codenuclear.com/leetcode-counting-elements-30days-challenge
- EG
- SUMMA
- loop eles (orig_arr)
- if 1 zero, skip_this_zero; if >= 2 zeros, no_skip
- if orig_arr.includes(2*ele); re true; (loop_each_ele, mod_to_use)
- https://leetcode.com/problems/check-if-n-and-its-double-exist
- EG
- SUMMA
- loop eles
- if set.con(2*ele) || set.con(ele/2), re true; (loop_each_ele, mod_to_use)
- else set.add(ele)
- https://leetcode.com/problems/check-if-n-and-its-double-exist
- EG
- SUMMA
- re CHINA || China || china
- loop chars
- re up_ups(w) || up_lows(w) || low_lows(w);
- up_ups == up?(w[0]) && up?(w[i], loop)
- up_lows == up?(w[0]) && low?(w[i], loop)
- low_lows == low?(w[0]) && low?(w[i], loop)
- https://leetcode.com/problems/detect-capital
query_arr(like_2D), words_arr(like_2D); query_smallest_dist_arr, word_smallest_dist_arr; in_loop, out_loop
query_arr(like_2D), words_arr(like_2D); query_smallest_dist_arr, word_smallest_dist_arr; in_loop, out_loop
- EG
- qs -> [aza, bab]; ws -> [czzc, ddz]
- qs1 -> [3_a_dist, 1_a_dist]; ws1 -> [4_c_dist, 2_d_dist]
- res -> [1, 2]
- 3_a_dist < 4_c_dist(*), 3_a_dist > 2_d_dist(x), so 1)
- 1_a_dist < 4_c_dist(*), 1_a_dist < 2_d_dist(*), so 2)
- SUMMA
- qs_sort, find_smallest, a[0]
- ws_sort, find_smallest, a[0]
- dist = lastInd(a[0]) - ind(a[0]) + 1
- qs1 -> [3_a_dist, 1_a_dist]; ws1 -> [4_c_dist, 2_d_dist]
- out_loop, in_loop; qs1[0], qs1[1] stay
- https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character
outloop, inloop; use_up single def_num, 3999 -> 2999 -> 1999 -> 999 -> 99 -> 9 -> 0 === (MMM)(CM)(?)(?)
- EG
- 3999 -> 2999 -> 1999 -> 999 -> 99 -> 9 -> 0
- SUMMA
- def_num (hash)
- const h = { 1: "I", 4: "IV", .. 9: "IX", .. 90: "XC", ... 900: "CM" 1000: "M" }
- hash -> arr -> rev
- outloop: loop each def_num
- inloop: use_up single def_num, move next
- num -> roman, build str
- https://leetcode.com/problems/integer-to-roman
- EG
- SUMMA
- outloop: while(prev_s.len !== curr_s.len)
- inloop: (i=0, i+1<s.len); s[i+1] - s[i] == 32, s.rm('Aa')
- A - a = 32, B - b = 32...
- https://leetcode.com/problems/make-the-string-great
- EG
- ..
- SUMMA
- len = 6, half_len = 3
- abcabc (len_1(stable), OUTLOOP)
- a VS b, a VS c, a VS a, a VS b, a VS c (slide_char, INLOOP)
- abcabc (len_2(stable), OUTLOOP)
- ab VS ca, ab VS bc (slide_char, INLOOP)
- abcabc (len_3(stable), OUTLOOP)
- abc VS abc (slide_char, INLOOP)
- outloop: pattern
- inloop: move pattern
- https://leetcode.com/problems/repeated-substring-pattern
- EG
- SUMMA
- loop words
- ..
- aabc, [ab, bc] -> [0, 1, 1, 1] (orig ab -> 11; orig bc -> 11)
- ..
- https://massivealgorithms.blogspot.com/2017/06/leetcode-616-add-bold-tag-in-string.html
- EG
- SUMMA
- loop chars
- RLLLRR, (+1)(-1)|(-1)(-1)(+1)(+1), res == 2; (orig, L, R -> -1, +1)
- https://leetcode.com/problems/split-a-string-in-balanced-strings
- EG
- SUMMA
- loop chars (e.g. LLRRUD, robot move)
- back_to_zero(MULTI); ++vertical, --vertical; ++horizontal, --horizontal
- https://leetcode.com/problems/robot-return-to-origin
- EG
- SUMMA
- loop words
- slide_word (j, j+len), (s.len - w.len, dynamic_len)
- substring_equal
- fill_substring
- start_loop,
- mid_loop: greedy
- end_loop,
- https://massivealgorithms.blogspot.com/2017/06/leetcode-616-add-bold-tag-in-string.html
- EG
- SUMMA
- loop words
- slide_word (j, j+len), (s.len - w.len, dynamic_len)
- substring_equal
- res.sort
- https://medium.com/algorithm-and-datastructure/index-pairs-of-a-string-7b7c8306ead0
- EG
- SUMMA
- [0(0, sh=0), 0(1, sh=1), 0(2, sh=2), 0(3, sh=3), 1(4)], len = 5;
- shift(prev_0s) + ind < len ===> 2 + 2 = 4 < 5
- shift(prev_0s) + ind < len ===> 3 + 3 = 6 > 5 (build_knowledge, # shift)
- loop_stop, sh == 3 (1 extra)
- loop(i=i-1; sh>0 ..) (backward)
- if i+sh < len (avoid 1 extra); read i, write i+sh (normal, i_read, i_write_almost)
- if a[i] == 0; read i, write i+(--sh) (dup 0, i_read, i_write_almost)
- https://leetcode.com/problems/duplicate-zeros/discuss/312743/JavaC%2B%2B-O(n)-or-O(1)
- EG
- a1: [3, 4, 1, 1, 2, 2]
- a2: [1, 2]
- h: {3:1, 4:1, 1:2, 2:2} (build_knowledge)
- out: [1, 1, 2, 2, 3, 4]
- SUMMA
- ..
- ..
- https://leetcode.com/problems/relative-sort-array
- EG
- SUMMA
- e.g. abc === abc, re -1, no uncommon
- e.g. abcde..... z VS abc, largest, uncommon
- https://leetcode.com/problems/longest-uncommon-subsequence-i
- EG
- SUMMA
- e.g. "abc"
- loop (i start; small)
- subloop (j end; big; i j cross over)
- sub(i, j)
- EG
- SUMMA
- loop ele
- subloop eles
- if not_same, not_in_res, substring, res.push
- https://leetcode.com/problems/string-matching-in-an-array
- EG
- SUMMA
- [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]]
- res = [[1_count, 0_ind], [4, 1], [1, 2], [1, 3]]
- res.sort(other_attr ? other_attr : default_attr);
- res.sort.slice.map: sort(other_attr ? other_attr : default_attr) -> slice_portion -> map_sub_attr)
- https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix
- EG
- SUMMA
- ..
- ..
- ..
- res.sort, [(0, 3), (0, 1), (1, 2), (1, 1)] -> [(0, 1), (0, 3), (1, 1), (1, 2)]
- https://medium.com/algorithm-and-datastructure/index-pairs-of-a-string-7b7c8306ead0
- EG
- (ab)abab vs ab, ababab.sub(ab.len) == abab; abab vs ab
- (ab)ab vs ab, abab.sub(ab.len) == ab; ab vs ab
- ab vs ab, ab.sub(ab.len) == ''; gcd
- SUMMA
- long - short, keep going
- recur
- (1) long_var (maintain meaning) > short_var (maintain meaning); (2) false_case( !abab.sub(ab) ); (3) good_case( s1 there, s2 == '' ); (4) con( (ab)ab, ab )
- https://leetcode.com/problems/greatest-common-divisor-of-strings
- EG
- SUMMA
- get_letter_arr(split, filter, isNaN), get_num_arr(split, filter, isNaN)
- big_var (maintain meaning) > small_var (maintain meaning)
- (bs)(bs)(b), bs + bs + extra
- (bs)(bs), bs + bs + no_extra
- arr.pop_end()
- https://leetcode.com/problems/reformat-the-string
- EG
- SUMMA
- loop chars
- if cap; 'a'.charCodeAt(0) + (s[i] - 'A'.charCodeAt(0)), to_num; fromCharCode, to_char
- distance(c - a) === distance(C - A)
- https://leetcode.com/problems/to-lower-case
- EG
- SUMMA
- special case 1st, then normal case; s.replace(/10#/)
- https://leetcode.com/problems/decrypt-string-from-alphabet-to-integer-mapping
- EG
- AAAA - AAA = A;
- AAA - A = AA;
- AA - A = A;
- A - A = 0 (done)
- SUMMA
- gcd_recur
- if short_str.len > long_str.len (keep short_before_long)
- if long.index(short) === 0, re ''; (long_has_no_short)
- if short.len === 0, re big; (short full consumed)
- else gcd( long.substr(short), short ); (gcd_recur_rm_common)
- https://leetcode.com/problems/greatest-common-divisor-of-strings
keep start_before_end; curr_res in total_res, when_condi; total_res_with_loop; part_cycle = curr_res; rest_part_cycle = tot_res - curr_res
- EG
- [1_distance, 2_d, 3_d, 4_d]; 1_ind -> 2_ind, 2_distance
- SUMMA
- if start_ind > end_ind; swap; keep_1_direction_cycle
- loop eles
- if i >= start_ind(0_ind) && i < dest_ind(1_ind); res = res + dist[i] (curr_res in total_res, when_condi)
- tot = tot + dist[i] (total_res_with_loop)
- end_loop; part_of_cycle = curr_res; rest_part_of_cycle = tot_res - curr_res
- https://leetcode.com/problems/distance-between-bus-stops
https://leetcode.com/discuss/general-discussion/491522/dynamic-programming-questions-thread
- dp[i] === AT this ele (num_char), FINAL num_combo
- init side === 1 (num_combo_1D; flow down)
- loop ele (num_char)
- curr_digit (0 skip; 1 good flow down)
- curr_digit in 1->9(single_char); dp[i] = dp[i-1](curr digit flow down);
-
- p_digit + curr_digit (undef_0 skip; undef_1 skip; "12" good flow)
- p_digit + curr_digit in 10->26(double_char); dp[i] = dpi + i>=2 ? dp[i-2](2 digit flow down)
- SUMMRY
- curr_digit, done; p_digit + curr_digit, done
- https://leetcode.com/problems/decode-ways
- dp[i] = dp[i_prev] + curr_ele
- dp[i] = dp[i_prev] + func(curr_ele)
- dp[i] = reset + curr_ele
aaabc -> aaa_3_char, aa_2_char, a_1_char, b_1_char, c_1_char -> 3+2+1+1+1=8; dp[i]_curr_freq = dp[i-1]_prev_freq + dp[i]_curr_freq
- EG
- SUMMA
- single_loop (i=1_look_back; i<len...)
- DP_EXPLAIN
- dp_slot == arr.len
- dp[a.len].fill(1) == 1_char_freq
- i == curr_ind
- dp[i] == curr_freq
- i-1 == prev_ind
- dp[i-1] == prev_freq
- single_loop (i=1_look_back; i<len...)
- dp[i]_curr_freq = dp[i-1]_prev_freq + dp[i]_curr_freq
- https://helloacm.com/counting-substrings-with-only-one-distinct-letter-with-different-algorithms
N = 12; 1 -> 0(0), 2 -> 5(1), 3 -> x(0)... 10 -> 10(0), 11 -> 11(0), 12 -> 15; contain [3, 4, 7], then*all_fail; contain [2, 5, 6, 9], then_give_1
-
EG
-
mycount
-
0 1 2 3 4 5 6 7 8 9 10 11 12 13 (each_num)
-
0 1 5 x x 2 9 x 8 6 10 11 12 1x (e.g. 2 -> 5, 180 degrees)
-
0 0 1 0 0 1 1 0 0 1 00 00 01 00 (contain [3, 4, 7], then_all_fail; contain [2, 5, 6, 9], give_1)
-
double_digits
-
14 -> 1(1)4(x) -> 0 (contain [3, 4, 7], then_all_fail)
-
20 -> 2(1)0(0) -> 1 (contain [2, 5, 6, 9], give_1)
-
22 -> 2(1)2(1) -> 1 (......)
-
SUMMA
-
contain [3, 4, 7], then_all_fail
-
contain [2, 5, 6, 9], then_give_1
-
single_loop(i=1; i<=N...)
-
DP_EXPLAIN
-
dp_slot == N+1
-
dp[N+1].fill(0)
-
i == curr_input_num
-
dp[i] == curr_rotate_addup
-
i-1 == prev_input_num
-
dp[i-1] == prev_rotate_addup
-
dp[i] = dp[i-1] + mycount(i)
00000 0 0 0 0
01000 0 0 0 0
00000 1 0 0 0
11111 0 0 0 0
10000 1 1 1 1
11111 1 1 1 1
00000 01 0 0 0
00000 01111 0 0 0
00000 01 01 01 01
00000 01111 01 01 01
11111 1 1 1 1
- n+1, m+1 size
- dp[i][j] => AT THIS row, AT THIS col, FINAL num_combo
- init side => physi_1_1_val(num_combo) || fake_top_1_val || fake_left_1_val;
- loop row (n)
- loop col (m)
- dp[i][j] = dp[i-1]j + dp[i]j-1; add
- re dp[n][m]
- https://leetcode.com/problems/unique-paths/
- m+1 size
- dp[i] => AT THIS col, FINAL num_combo
- init side => physi_1_1_val(num)combo
- loop row (n)
- loop col (m)
- dp[j] = dp[j](top; press_row) + dp[j-1](left, press_row)
- re dp[m]
- https://leetcode.com/problems/unique-paths/
- n+1, m+1 size
- dp[i][j] => AT this row, AT this col, FINAL num_combo
- init side => physi_1_1_val(num_combo); dp[1][1] == 1 || 0 (dep obstacle); init_in_loop
- loop row (n)
- loop col (m)
- if obstacle, dp[i][j] = 0 (self no)
- else no obstacle, dp[i][j] = dp[i-1]j + dp[i]j-1;
- re dp[n][m]
- https://leetcode.com/problems/unique-paths-ii/
- m+1 size
- dp[j] => AT this col, FINAL num_combo
- init side => physi_1_1_val(num_combo); dp[1] == 1 || 0 (dep obstacle); init_in_loop
- loop row (n)
- loop col (m)
- if obstacle, dp[j] = 0 (self no)
- else no obstacle, dp[j] = dp[j](top; press_row) + dp[j-1](left; press_row);
- re dp[m]
- https://leetcode.com/problems/unique-paths-ii/
- n+1, m+1 size
- dp[i][j] => AT this col, AT this row, FINAL min_path
- init side => during_loop
- loop row (n)
- loop col (m)
- if 1st row, dp[i][j] = dp[i]j-1 + grid[i-1][j-1]
- if 1st col, dp[i][j] = dp[i-1]j + grid[i-1][j-1]
- else dp[j] = MIN(dp[i]j-1, dp[i-1]j) + grid[i-1][j-1]
- https://leetcode.com/problems/minimum-path-sum/
- m+1 size
- dp[i][j] => AT this col, AT this row, FINAL min_path
- init side => during_loop
- loop row (n)
- loop col (m)
- if 1st row, dp[j] = dp[j-1](left; press_row) + grid[i-1][j-1]
- if 1st col, dp[j] = dp[j](top; press_row) + grid[i-1][j-1]
- else dp[j] = MIN(dp[j-1](left; press_row), dp[j](top; press_row)) + grid[i-1][j-1]
- https://leetcode.com/problems/minimum-path-sum/
- EG
- rowNum = 4, so [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
- SUMMA
- dp[i][j] => i at this rowNum, i=0, i<=rowNum-1;
- dp[i][j] => j at this content, j=1(avoid head), j<i(avoid tail);
- dp[i][j] => res
- out_loop rowNum
- pa = [] (build_1D)
- in_loop content (avoid head / tail)
- pa[i] = [] (build_2D); pa[i][0] = 1(start)
- pa[i][j] = pa[i-1]j-1 + pa[i-1]j
- pa[i][i] = 1(end)
- https://leetcode.com/problems/pascals-triangle
- n, m size (dp_size == ma_size)
- dp[i-1][j] => AT this col, AT this row, FINAL min_path
- init side => fill_bottom_row
- loop row (bottom_up; i=n-1(ele); i>=0(ele))
- loop col (bottom_forward; j=0; j>=i(j+1))
- dp[i-1][j] = MIN(dp[i-1][j], dp[i-1][j+1]) + grid[i-1]j
- re dp[0][0]
- https://leetcode.com/problems/triangle
- m size
- dp[j] => AT this col, FINAL min_path
- init side => fill_bottom_row
- loop row (bottom_up; i=n-1(ele); i>=0(ele))
- loop col (bottom_forward; j=0; j>=i(j+1))
- dp[j] = MIN(dpj, dpj+1) + grid[i-1][j]
- re dp[0]
- https://leetcode.com/problems/triangle/
- n+1, m+1, z+1 size
- dp[k][i][j] === AT this ele, AT this tar_m, AT this tar_n, FINAL max_combo
- init side === 0 (max_nopress, so 0s; below_val)
- loop ele (forward, NO_ORDER)
- loop tar_m (forward)
- loop tar_n (forward)
- direction
- j >= zero && k >= one, dp[k][i][j] = ma( dp[i-1][j][k](top, ele_1st), 1 + dp[i-1][j-zero][k-one](diag, init_noval, val(1)) )
- else, dp[k][i][j] = dp[i-1][j][k](top, ele_1st)
- https://leetcode.com/problems/ones-and-zeroes/
- n+1, m+1 size
- 3D; dp[dice][face][tar] => AT this dice, AT this face, AT this tar, FINAL num_combo(add)
- 2D, press_ele; dp[i][j] => AT this dice, AT this tar, FINAL num_combo(add)
- init side => physi_1_1_val (num_combo_press, so 1; below_noval)
- loop dice (forward)
- loop tar (forward; ORDER, 1+2, 2+1, diff)
- loop face (forward; ele)
- direction
- j>=k, dp[i][j] = dp[i][j](orig, tar_1st, ORDER; press_ele) + dp[i][j-k(face)](left, num_combo; press_ele) % module;
- SUMMARY
- loop1, loop2, loop3 ORDER_DIFF dp[3][2][1]
- https://leetcode.com/problems/number-of-dice-rolls-with-target-sum
- m+1 size
- dp[j] => AT this num, FINAL max_product
- init side => 1 (multiply 1)
- loop ele (forward; NO_ORDER, 12, 21, same)
- loop tar (forward; dp_ind_constraint)
- direction
- dp[j] = MAX(dp[j](top, ele*1st; press*ele), dp[j-i](diag, init_x_formu_var; press_ele; x+y=tar) * i(x*y = max_product)), no_inject_vs
- https://leetcode.com/problems/integer-break
- m+1 size
- dp[i] => AT this num, FINAL min_combo
- init side => 0 (min_press, so 0; below_val)
- loop tar (forward; ORDER? 1^2 + 2^2, affect_next_diff)
- loop ele (forward; dp_ind_constraint)
- direction
- mi = mi( mi, dp[i-j*j](diag, init_noval, val(1); press_ele; x^2+y^2 = tar) + 1 ), inject_vs
- end_loop_up_dp
- https://leetcode.com/problems/perfect-squares
- m+1 size
- dp[i] => AT this len, FINAL max_val
- init side => 0 (max_press, so 0; below_val)
- loop tar (forward; ORDER, len1v, len2v, order_diff)
- loop ele (forward; dp_recal_constraint)
- direction
- dp[i] = MAX(dp[i](orig, tar_1st, ORDER; press_ele), dp[i-j(ele)](diag, init_noval, val(w); press_ele; x+y=sub_tar) + price_arri-j )
- https://www.lintcode.com/problem/cutting-a-rod
- https://www.lintcode.com/discuss/1266/
- transfer: (a + b) - (c + d), (totTar - aTar) - aTar === diff; ha = sum / 2
- n+1, ha+1 size
- dp[i][j] === AT this ele, AT this tar, FINAL condi
- init side == fake_left_vals (condi_nopress, so trues; below_noval)
- loop ele (forward; NO_ORDER)
- loop ha (forward)
- direction
- dp[i][j] = dp[i-1][j](top, ele_1st) || dp[i-1][j-i](diag, condi; x+y=ha); ma VS j(sub_tar), inject_vs
- https://leetcode.com/problems/last-stone-weight-ii/
- transfer: ha = sum / 2
- ha+1 size
- dp[j] === AT this ha; FINAL condi (question min_diff; dp[j] == true, to_update_max)
- init side == true (condi_press, so true; below_noval)
- loop ele (forward; NO_ORDER, 1+2, 2+1, same)
- loop ha (backward, 1d_gen_tar; dp_ind_constraint)
- direction
- dp[j] = dp[j](top, ele_1st; press_ele) || dp[j-i(ele)](diag, condi; press_ele; x+y=ha); ma VS j(sub_tar), inject_vs
- https://leetcode.com/problems/last-stone-weight-ii/discuss/635621/Dp-solution-with-explaination-(cpp)
- transfer: s(#) = [1, 2, 3, 4, 5], tar = 3
- s(#) = [+1, -2, +3, -4, +5], tar = 3
- (1+3+5) - (2+4) == 3 ====> s(+p) - s(+n) == tar
- s(+p) - s(+n) + s(#) == tar + s(#)
- s(+p) - s(+n) + s(+p) + s(+n) == tar + s(+p) + s(+n)
- 2 * s(+p) == tar + s(#)
- s(+p) == (tar + s(#)) / 2
- x
- x
- m+1 size
- dp[j] === AT this ha, FINAL num_combo(add)
- init side == 1 (num_combo_press, so 1; below_noval)
- loop ele (forward; NO_ORDER, 1+2, 2+1, same)
- loop ha (backward, 1d_gen_tar; dp_ind_constraint)
- direction
- dp[j] = dp[j](top, ele_1st; press_ele) + dp[j-i(ele)](left, num_combo_left; press_ele; x+y=tar)
- https://medium.com/swlh/solving-the-target-sum-problem-with-dynamic-programming-and-more-b76bd2a661f9
- https://leetcode.com/problems/target-sum/discuss/97334/Java-(15-ms)-C%2B%2B-(3-ms)-O(ns)-iterative-DP-solution-using-subset-sum-with-explanation
- EG
- SUMMA
- dp[0] = 1 (start)
- dp[i+1] = 1 (push_new_end)
- dp[j] => j at this num; j=i(backward, 2nd_last), j>0(avoid_head)
- dp[j] => res
- out_loop numRow (top -> bottom)
- dp[0] = 1 (start)
- dp[i+1] = 1 (push_new_end)
- in_loop #; j=i(backward, curr_overwrite, prev_nochange; 2nd_last), j>0(avoid_head)
- dp[j] = dpj-1 + dpj
- https://leetcode.com/problems/pascals-triangle-ii
- n+1, m+1 size
- dp[i][j] => AT this child_char; AT this parent_char; FINAL condi(chop_char_subseq);
- init side => fake_top_vals (each_child_use_diag)
- loop child (child_1st, each_child_use_diag)
- loop parent
- direction
- if, dp[i][j-1](left, each_child_use_diag) == true, dp[i]j = true
- if, dp[i-1][j-1](diag, each_child_use_diag) == true && c[i] == p[j](char == char), dp[i]j = true
- https://leetcode.com/problems/is-subsequence/
- m+1 size
- dp[i] === AT str posi; FINAL condi(from question)
- init side === true (condi_press, so true; below_noval)
- loop parent (parent_1st, child_build_parent)
- loop child
- direction
- dp[i] = ( dp[i](orig, tar_1st, ORDER; press_child) || ( dp[i - w_l](left, p_w + c_w == f_w; press_child; w_l + rest = fw_l) && s.sub == w(word_match) ) )
- https://leetcode.com/problems/word-break
- n+1, m+1 size
- dp[i][j] === AT this ele, AT this tar, FINAL num_combo
- init side => fake_left_vals (num_combo_nopress, so 1s; below_noval)
- loop ele (forward; NO_ORDER)
- loop tar (forward)
- direction
- j>=i(w), dp[i][j] = dp[i-1][j](top, ele_1st) + dp[i][j-i(ele)](left, num_combo_left)
- else, dp[i][j] = dp[i-1]j
- https://leetcode.com/problems/coin-change-2/
- m+1 size
- dp[j] === AT this tar, FINAL num_combo
- init side === 1 (num_combo_press, so 1; below_noval)
- loop ele (forward; NO_ORDER, 1+2, 2+1, same)
- loop tar (forward, dp_ind_constraint)
- direction
- dp[j] = dp[j](top, ele_1st; press_ele) + dp[j-i(ele)](left, num_combo_left; press_ele; x+y=tar);
- https://leetcode.com/problems/coin-change-2/
- n+1, m+1 size
- dp[i][j] === AT this ele, AT this tar, FINAL min_num_combo
- init side === 0 (min_nopress, so 0s; below_val)
- loop ele (forward)
- loop tar (forward)
- direction
- j>=i(w): dp[i][j] = mi( dp[i-1][j](top, ele_1st, NO_ORDER), 1 + dp[i][j-i(ele)](left, num_combo_left) )
- else: dp[i][j] = dp[i-1][j]
- https://leetcode.com/problems/coin-change/
- m+1 size
- dp[j] => AT this num, FINAL min_num_combo/-1
- init side => 0 (min_press, so 0; below_val)
- loop ele (forward; NO_ORDER, 1+2, 2+1, same)
- loop tar (forward; dp_ind_constraint, j=w; j<=t)
- direction
- dp[j] = MIN(dp[j](top, ele_1st, NO_ORDER; press_ele), 1 + dp[j-i(ele)](left, num_combo_left; press_ele; x+y=tar) )
- https://leetcode.com/problems/coin-change/
- EG
- SUMMA
- dp[i] => i, at each index
- dp[i] => dp[i], cost so far
- dp[i-1] => prev_step_1, acc_cost
- dp[i-2] => prev_step_2, acc_cost
- dp[x-y] => none
- dp[0] => init, start_0 (2_start)
- dp[1] => init, start_1 (2_start)
- ns[i] => ele, curr_cost
- loop eles (i=2, i<len)
- dp[i] = mi(dp[i-1], dp[i-2])(2_start) + ns[i]
- re mi(dp[len-1], dp[len-2]) (2_ending)
- https://leetcode.com/problems/min-cost-climbing-stairs
- EG
- climb, take_1_step or take_2_step
- SUMMA
- draw_the_tree_cache
- init:
- recur_cache VS dp_arr
- dp[0]: when_tar_exhaust
- single_loop:
- recur_func VS dp_func
- sub_tars contrib top_tar; count = count + recur(sub_tar)_abstract_return
- sub_tars_cache
- https://leetcode.com/problems/climbing-stairs
- EG
- climb, take_1_step or take_2_step
- SUMMA
- draw_the_tree_dp
- init:
- dp_arr VS recur_cache
- dp[0]: when_tar_exhaust
- outloop:
- bottom -> top VS top -> bottom -> slow_cover_top
- inloop:
- dp_func VS recur_func
- sub_tars contrib top_tar: dp[tar] = dp[tar-ns[0]] + dp[tar-ns[1]] + dp[tar-ns[2]]... -> dp[tar] = dp[tar]_acc_inloop + dp[tar-ns[i]];
- avoid_ind_overconsume
- https://leetcode.com/problems/climbing-stairs
- EG
- SUMMA
- method 1:
- draw_the_tree_no_cache
- knapsack recur; recur_as_loop_i
- method 2:
- draw_the_tree_2d_cache
- knapsack recur, recur_as_loop_i
- method 3:
- 2d_cache
- same as above, 2d_cache(dp[i][tar] == dp[tar][i])
- method 4:
- 2d_cache
- combination_sum recur, no recur_as_loop_i
- method 5:
- 2d_cache
- tar -> ele (order important; want_more dp[..][len])
- ele -> tar (order !important; want_less dp[..][j-1]; loop_order_can_swap) <--
- method 6:
- 2d_cache
- tar -> ele (order important; want_more dp[..][len]) <--
- ele -> tar (order !important; want_less dp[..][j-1]; loop_order_can_swap)
- method 7:
- 1d_cache
- backward_loop, use_prev_dp; forward_loop, overwritten_prev_dp
- see my solution: https://leetcode.com/submissions/detail/468284357
- https://leetcode.com/problems/partition-equal-subset-sum
- EG
- SUMMA
- method 1:
- draw_the_tree_no_cache(timeout); recur_abstract_return
- method 2:
- 1d_cache
- draw_the_tree_cache; recur_abstract_return
- method 3:
- 2d_cache
- tar -> ele (order important; want_more, dp[..][j-1]) <--
- ele -> tar (order !important; want_less, dp[..][len]; loop_order_can_swap) x
- method 4:
- 1d_cache
- forward_loop, no_overwritten_prev_dp (dp[..][len])
- method 5:
- 1d_cache
- backward_loop, use_prev_dp
- my solution: https://leetcode.com/submissions/detail/468503374/
- https://leetcode.com/problems/combination-sum-iv
- EG
- SUMMA
- method 1:
- dp[ind][can_buy] = buy or no_action; dp[ind][can_buy] = sell or no_action; k_tran = unlimit (so no care)
- method 2:
- recur == dp, some_param == dp_ind, ele == ele
- method 3:
- 1D_dp, order important; recur == dp; some_param == dp_ind; ele == ele
- method 4:
- const_var; recur == dp; some_param == dp_ind; ele == ele
- method 5:
- peak-valley; find_bottom, ind_exceed_condi; find_top, ind_exceed_condi;
- https://leetcode.com/submissions/detail/474057458/
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
- EG
- SUMMA
- method 1:
- brute_force; i_stable, j_stable, k_loop (everytime_startover_subarray)
- method 2:
- brute_force; i_stable, j_loop, exhaust (everytime_prev_subarray)
- method 3:
- dp; curr = (con_subarray || startover_subarray) + ele
- method 4:
- dp; curr = (con_subarray || startover_subarray) + ele; dp[i], dp[i-1] using_same_var
- https://leetcode.com/submissions/detail/472100127/
- https://leetcode.com/problems/maximum-subarray
- EG
- SUMMA
- method 1:
- brute_force; i_stable vs j_loop
- method 2:
- big_segment == small_segments (prepare), then max_subarray problem
- method 3:
- big_segment == small_segments (in_fly), then max_subarray problem
- method 4:
- i vs i-1 partition (1_min)
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock
- EG
- SUMMA
- brute_force; all_step map 2D dp; i_start, j_end -> range
- https://leetcode.com/problems/longest-palindromic-substring
- EG
- SUMMA
- brute_force; at curr_i, look left, look right
- https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/
- EG
- [1, 2, 3, 4, 5], k = 3 -> [3, 2, 1, 5, 4]
- SUMMA
- build_fresh (inject); i_start, j_end (j backward inject)
- j abstract (inbound or outbound)
- https://practice.geeksforgeeks.org/viewSol.php?subId=2654ac371c531fa9fb2c06f5690a0623&pid=701191&user=figo2476
- https://practice.geeksforgeeks.org/problems/reverse-array-in-groups0255/1
- EG
- SUMMA
- 2pt, max_hold_most_water (left), max_hold_most_water (right); small_move (already consumed)
- https://leetcode.com/submissions/detail/495366729/
- https://leetcode.com/problems/trapping-rain-water
- EG
- SUMMA
- 2pt, skip_loop (i_start), skip_loop (j_end); rev; next
- https://leetcode.com/submissions/detail/410447049/
- https://leetcode.com/problems/reverse-words-in-a-string-iii
even num on left, odd num on right; skip_loop (hit odd), skip_loop (hit even), swap; even_left, odd_right (in place)
- EG
- SUMMA
- skip_loop (hit odd), skip_loop (hit even), swap; even_left, odd_right
- https://leetcode.com/problems/sort-array-by-parity
even num on left, odd num on right; build_fresh, i_write (start), j_write (end), n_read; left_partition_even, right_partition_odd (fresh)
- EG
- SUMMA
- build_fresh (easier), i_write (start), j_write (end), n_read; left_partition_even, right_partition_odd
- https://leetcode.com/problems/sort-array-by-parity
- EG
- SUMMA
- skip_loop (non-alpha-num); i_start == j_end, cross; brute_force
- https://leetcode.com/problems/valid-palindrome
even num at even ind, odd num at odd ind; build_fresh (easier), i_write (start), j_write (start), n_read; even at even, odd at odd
- EG
- SUMMA
- build_fresh (easier), i_write (start), j_write (start), n_read; i (correct_posi), j (correct_posi)
- https://leetcode.com/problems/sort-array-by-parity-ii/
- EG
- SUMMA
- 2pt, i_start (stable), j_start (extending); brute_force; can_exist_early (+)
- https://practice.geeksforgeeks.org/viewSol.php?subId=8667e105a253bc4200a06c456b6b0142&pid=701236&user=figo2476
- EG
- SUMMA
- 2pt, i_start, j_start (extending); range
- https://leetcode.com/submissions/detail/432859062/
- https://leetcode.com/problems/positions-of-large-groups/
- EG
- SUMMA
- 2pt, i_end, j_end (extending); backward, skip spaces
- https://leetcode.com/problems/length-of-last-word
- EG
- SUMMA
- 0 (k len rev); 1k (no); 2k (k len rev); 3k (no); 4k (k len rev); i+k_len (question_ask)
- j_end abstract
- https://leetcode.com/problems/reverse-string-ii
- EG
- SUMMA
- i = i+2 (question_show)
- https://leetcode.com/problems/decompress-run-length-encoded-list
- EG
- SUMMA
- sort; i, i+len/2 (i vs i+len/2, then slide)
- https://leetcode.com/problems/majority-element
- EG
- SUMMA
- sort; i, i+len/2 (i vs i+len/2, then slide)
- https://www.geeksforgeeks.org/check-for-majority-element-in-a-sorted-array/
- EG
- SUMMA
- i=0; i<len+1;
- j=i+1; j<len; (no-check-self, 2_loop)
- https://leetcode.com/problems/longest-palindromic-substring/discuss/523015/Simple-brute-force
- https://leetcode.com/submissions/detail/516739706/
- EG
- SUMMA
- 2pt (lo -> small, hi -> large)
- https://leetcode.com/problems/di-string-match/
- EG
- SUMMA
- sort; i_start + j_end-1 = k_end (look for large)
- https://practice.geeksforgeeks.org/problems/count-the-triplets4615/1
- https://practice.geeksforgeeks.org/viewSol.php?subId=897008f882370645ad43ee369da48b30&pid=702837&user=figo2476
- EG
- SUMMA
- sort; i_start + j_end-1 == k_end* (look for large)
- https://practice.geeksforgeeks.org/viewSol.php?subId=e42971255da045373e53e797d7618dec&pid=702805&user=figo2476
- https://practice.geeksforgeeks.org/problems/pythagorean-triplet3018/1
- EG
- SUMMA
- sort; i_start* + i_start+1 + j_end == 0 (make it small)
- https://leetcode.com/problems/3sum
- EG
- SUMMA
- brute_force (i_stable, j_loop, exhaust); i, i+1 is local_inv and global_inv (neighbour); i, i+2.. is only global_inv (beyond neighbour)
- https://leetcode.com/submissions/detail/483848195/
- https://leetcode.com/problems/global-and-local-inversions
- EG
- SUMMA
- 3 consecutive odds; i-2, i-1, i*
- https://leetcode.com/problems/three-consecutive-odds
- EG
- SUMMA
- i-1, i*, i+1; i max swap; max_top
- https://practice.geeksforgeeks.org/problems/convert-array-into-zig-zag-fashion1638/1#
- EG
- SUMMA
- i-1, i*, i+1; inc "a" to 26 char;
- https://leetcode.com/problems/replace-all-s-to-avoid-consecutive-repeating-characters
- EG
- SUMMA
- i-1, i*, i+1; inc "a" to "c";
- https://leetcode.com/problems/replace-all-s-to-avoid-consecutive-repeating-characters
if not palindrome, rm 1 char; i_start, i_start+1, j_end-1, j_end ===> i_start, j_end-1 OR i_start+1, j_end
- EG
- SUMMA
- rm 1 char; i_start, i_start+1, j_end-1, j_end ===> i_start, j_end-1 OR i_start+1, j_end
- https://leetcode.com/submissions/detail/505923628/
- https://leetcode.com/problems/valid-palindrome-ii
- EG
- SUMMA
- brute_force (1 train stable, other train loop); cross_compare (a_end vs b_start)
- https://practice.geeksforgeeks.org/problems/minimum-platforms-1587115620/1
- https://practice.geeksforgeeks.org/viewSol.php?subId=a5d446a873521478733111306c0e77dd&pid=701368&user=figo2476
- EG
- SUMMA
- odd_num skip; i_stable, j_loop, exhaust; i_start, j_end (check valid)
- time limit exceed
- https://leetcode.com/submissions/detail/509678242/
- https://leetcode.com/problems/count-binary-substrings
aaaba; "a" 4, "aa" 2, "aaa" 1, "b" 1, so 8; i_stable, j_loop, exhaust (instead of count same_type, count as go)
- EG
- SUMMA
- 1 letter # consecutive; 2 letter # consecutive; 3 letter # consecutive, etc
- i_stable, j_loop, exhaust (instead of count same_type, count as go; eventually add up)
- https://helloacm.com/counting-substrings-with-only-one-distinct-letter-with-different-algorithms/
- EG
- SUMMA
- i_stable vs j_stable vs k_loop
- https://www.geeksforgeeks.org/count-triplets-with-sum-smaller-that-a-given-value
- EG
- SUMMA
- brute_force; efficiency, no-met-skip
- https://leetcode.com/submissions/detail/516739706/
- https://leetcode.com/problems/longest-palindromic-substring
- EG
- SUMMA
- ...
- EG
- SUMMA
- skip_loop (char, then dot)
- https://practice.geeksforgeeks.org/viewSol.php?subId=00cda62b9c4381b69883a0649c7bb704&pid=701308&user=figo2476
- https://practice.geeksforgeeks.org/problems/reverse-words-in-a-given-string5459/1
- EG
- SUMMA
- skip_loop (i_start, hit a e i o u; j_end, hit a e i o u), swap
- https://leetcode.com/problems/reverse-vowels-of-a-string
- EG
- SUMMA
- skip_loop (i_start, hit letter; j_end, hit letter), swap
- https://leetcode.com/problems/reverse-only-letters
- EG
- SUMMA
- method 1:
- skip_loop (all the way up); skip_loop (all the way down)
- method 2:
- skip_loop (all way up); skip_loop (all the way up, backward)
- https://leetcode.com/submissions/detail/497931700/
- https://leetcode.com/problems/valid-mountain-array
- EG
- SUMMA
- buy low (skip_loop), sell high (skip_loop); greedy
- https://leetcode.com/submissions/detail/498288319/
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
- EG
- SUMMA
- arr_ele <= c_res (no gap), arr_ele > c_res (gap)
- https://leetcode.com/problems/missing-ranges/
- https://medium.com/@rebeccahezhang/leetcode-163-missing-ranges-6ac21b477e96
- https://goodtecher.com/leetcode-163-missing-ranges/
- https://wentao-shao.gitbook.io/leetcode/array/163.missing-ranges
- EG
- SUMMA
- [3, 3, 3, 1, 1, 1, 2, 2, 2] -> [1, 1, 1, 2, 2, 2, 3, 3, 3]; sort -> curr_ind === how many smaller than you
- https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number
- EG
- SUMMA
- sort -> neighbour shortest
- https://leetcode.com/submissions/detail/510847420/
- https://leetcode.com/problems/minimum-absolute-difference
- EG
- SUMMA
- curr rating high > neighbours --> left neighbours (look_back, preserve prev), right neighbours (look_back, preserve prev); curr i max
- https://leetcode.com/problems/candy
- EG
- SUMMA
- max_hold_water (brute_force, left), max_most_water (brute_force, right); curr i min
- https://leetcode.com/submissions/detail/495366729/
- https://leetcode.com/problems/trapping-rain-water
- EG
- SUMMA
- max_hold_water (dp left), max_hold_water (dp right); curr i (max - curr)
- each_var_meaing;
- i: curr max so far
- i-1: prev..
- i+1: next..
- 0: init self
- n-1: last max
- dp[i]: curr max so far
- dp[i-1]: ..
- dp[i+1]: ..
- dp[0]: init self
- dp[n-1]: last ..
- f: max so far
- https://leetcode.com/submissions/detail/495366729/
- https://leetcode.com/problems/trapping-rain-water
- EG
- SUMMA
- left_max (dp left), right_max (dp right); curr i (compare left right, no curr i)
- https://practice.geeksforgeeks.org/viewSol.php?subId=a606567724872fdd52f0f7f36e3e68a0&pid=703327&user=figo2476
- https://practice.geeksforgeeks.org/problems/unsorted-array4925/1
brute_force; dp[ind][can_buy][tran] = buy or no_action; dp[ind][can_buy][tran] = sell or no_action; k_tran = 1, 2, k, unlimit
- EG
- SUMMA
- dp[ind][can_buy][tran] = buy or no_action; dp[ind][can_buy][tran] = sell or no_action; k_tran = 1
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock
- EG
- SUMMA
- dp[ind][can_buy][tran] = buy or no_action; dp[ind][can_buy][tran] = sell or no_action; k_tran = 2
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii
- EG
- SUMMA
- dp[ind][can_buy][tran] = buy or no_action; dp[ind][can_buy][tran] = sell or no_action; k_tran = k
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv
dp[ind][can_buy] = buy or no_action; dp[ind][can_buy] = sell or no_action; k_tran = unlimit (no care)
- EG
- SUMMA
- dp[ind][can_buy] = buy or no_action; dp[ind][can_buy] = sell or no_action; k_tran = unlimit
- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii
- EG
- SUMMA
- combo_sum_1 (i; non_0 no_repeat; unlimit so i)
- https://leetcode.com/problems/combination-sum
- EG
- SUMMA
- combo_sum_2 (i+1; use_once)
- look_back, before_op
- https://leetcode.com/problems/combination-sum-ii
- EG
- SUMMA
- combo_sum_3 (i+1 && len)
- https://leetcode.com/problems/combination-sum-iii
- EG
- SUMMA
- combo_sum_3 (draw_the_tree cache / dp)
- https://leetcode.com/problems/combination-sum-iv
- EG
- SUMMA
- sort
- k_stable; i, j meet
- < k (less_k)
-
= k
- https://kennyzhuang.gitbooks.io/leetcode-lock/content/259_3sum_smaller.html
- https://leetcode.com/problems/3sum-smaller
- EG
- SUMMA
- sort
- k_stable; i, j meet
- < k (less_k)
-
= k
- https://www.geeksforgeeks.org/count-triplets-with-sum-smaller-that-a-given-value/
- EG
- SUMMA
- sort
- k_stable; i, j meet
- < k (less_k)
-
= k
- https://leetcode.com/problems/3sum-closest
- EG
- SUMMA
- (1) rev_whole (later rev each_block)
- (2) rev_each_word (question ask); consume, stop
- (3) no_extra_space (trim_end, 1_each_word); j_read, i_write (non-move easily, write_at_correct_posi)
- https://leetcode.com/submissions/detail/410433342/
- https://leetcode.com/problems/reverse-words-in-a-string
reverse words in str; rev_whole, rev_each, no_space; whole then small_modifya good __ example " -> "example good a"; rev_whole, rev_each_word, no_extra_space
- EG
- SUMMA
- same above
- (1) rev_whole
- (2) rev_each_word
- (3) no_extra_space
- https://www.programcreek.com/2014/05/leetcode-reverse-words-in-a-string-ii-java/
- https://leetcode.com/problems/reverse-words-in-a-string-ii
- EG
- SUMMA
- i_write (correct_posi), j_read (explode)
- https://leetcode.com/submissions/detail/420662665/
- https://leetcode.com/problems/remove-duplicates-from-sorted-array
- EG
- SUMMA
- i_write (correct_posi), j_read (explode)
- https://leetcode.com/problems/remove-element
- EG
- SUMMA
- i_write (correct_posi), j_read (explode)
- https://leetcode.com/submissions/detail/493858027/
- https://leetcode.com/problems/move-zeroes
ns1 = [5, 6, 0, 0, 0], m = 2, ns2 = [1, 2, 3], n = 3 -> [1, 2, 3, 5, 6]; i_read (explode), j_read (explode), k_write (correct_posi)
- EG
- SUMMA
- i_read (backward_explode, won't overwrite), j_read (backward_explode, won't overwrite), k_write (non-move easily, write_at_correct_posi)
- https://leetcode.com/problems/merge-sorted-array
"abba" -> "aa" -> ""; rm 2 chars, new dup; j_read (explode), i_write (back / forward); build_from_ground
- EG
- SUMMA
- rm 2 chars, new dup; j_read (explode), i_write (back / forward); build_from_ground
- https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string
- EG
- SUMMA
- rm 2 chars, new dup; redo (outerloop)
- https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string
- EG
- SUMMA
- rm 2 chars, new dup; stack (close ele move together)
- https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string
- EG
- SUMMA
- sort; can this cookie feed this child? then_next
- https://leetcode.com/problems/assign-cookies/
- EG
- SUMMA
- ind = num % len;
- https://leetcode.com/problems/distribute-candies-to-people
- EG
- SUMMA
- i_start == j_end
- https://leetcode.com/problems/valid-palindrome
- EG
- SUMMA
- 1 -> 12 -> 121 (build, then compare, compare later)
- prev_digit = input / 10; curr_digit = input % 10;
- https://leetcode.com/problems/palindrome-number
- EG
- aabbaa -> 1 step, rm everything (palindr subseq)
- aaa -> 1 step, .. (palindr subseq)
- aaba -> 2 step, (a alone is palindr subseq; b alone ..)
- SUMMA
- palindr subseq (start, end same; non-con), rm 1 go
- https://leetcode.com/problems/remove-palindromic-subsequences
- EG
- SUMMA
- palindrome 2 sides + mid; "a" pal; "aa" pal; "a?a" pal; "a??a", prev dp;
- https://leetcode.com/problems/longest-palindromic-substring
- https://leetcode.com/submissions/detail/517268107/
- EG
- SUMMA
- [99,77,33,66,55], 33 is min, sum is 6 (even_num);
- prev_digit = input / 10; curr_digit = input % 10;
- https://bloggie.io/@rugved/leetcode-1085-sum-of-digits-in-the-minimum-number-java-solution
- https://leetcode.com/problems/sum-of-digits-in-the-minimum-number
" this is a sentence " -> "this is a sentence__"; len / num = each, len % num = remain; combine_words
- EG
- SUMMA
- len / num = each, len % num = remain; combine_words
- https://leetcode.com/problems/rearrange-spaces-between-words
- EG
- SUMMA
- full_len - ind == rest_len; rest_len % 3 == 0
- https://leetcode.com/problems/thousand-separator
- EG
- SUMMA
- sort
- sum - ele (chg_sth)
- become 2sum_hash_prev (become_old_question)
- matched, still_chance; 2sum_hash_prev
- https://leetcode.com/submissions/detail/470985485
- https://leetcode.com/problems/3sum
- EG
- SUMMA
- sort
- sum - ele (chg_sth)
- become 2sum_less_k (become_old_question)
- https://baihuqian.github.io/2018-07-28-3sum-smaller
- EG
- SUMMA
- sort
- half sum (change_sth)
- become combo_sum_2 (i+1) || combo_sum_3 (i+1, len)
- https://leetcode.com/problems/partition-equal-subset-sum
- EG
- SUMMA
- equal, means only local_inv exist (inverse_question)
- max_most_likely
- https://leetcode.com/submissions/detail/483848195/
- https://leetcode.com/problems/global-and-local-inversions
longest no repeated, "abcbk" -> chop "abc" -> "bk"; brute_force, str_tmp (indexOf), income_char dup?
- EG
- SUMMA
- brute_force, str_tmp (indexOf), income_char dup?
- https://leetcode.com/submissions/detail/546461793/
- https://leetcode.com/problems/longest-substring-without-repeating-characters
- EG
- SUMMA
- brute_force, hash (unique), income_char dup?
- https://leetcode.com/submissions/detail/546461793/
- https://leetcode.com/problems/longest-substring-without-repeating-characters
longest no repeated, "abcbk" -> chop "abc" -> "bk"; tmp_str (indexOf), right_end bit by bit, left_end indexOf reduce
- EG
- SUMMA
- tmp_str (reduce), right_end bit by bit, left_end indexOf reduce
- https://leetcode.com/submissions/detail/546461793/
- https://leetcode.com/problems/longest-substring-without-repeating-characters
(1) all_the_way: [1, 2, 3, 4], k = 10; (2) presum: [1, 2, 3, 4], k = 9; tmp_arr, right_end bit by bit, left_end loop reduce
- EG
- SUMMA
- tmp_arr (reduce), right_end bit by bit, left_end loop reduce
- https://practice.geeksforgeeks.org/viewSol.php?subId=66f55c983a16e914e59abcb7f5e74be6&pid=701236&user=figo2476
- EG
- SUMMA
- tmp_sum, right_end bit by bit, left_end loop reduce
- https://practice.geeksforgeeks.org/viewSol.php?subId=09bbc614f0fddbefbb19230a22824ec8&pid=701236&user=figo2476
- https://practice.geeksforgeeks.org/problems/subarray-with-given-sum-1587115621/1
- EG
- SUMMA
- right_end bit by bit, left_end hash reduce
- check?
-
- after reduce, check
-
- after win inc, check
- https://leetcode.com/submissions/detail/546461793/
- https://leetcode.com/problems/longest-substring-without-repeating-characters
[1, 2, 3, 4], k = 10, product < 10; [1], [1, 2], [2], etc; slide_win, right_end bit by bit, left_end loop reduce;
- EG
- SUMMA
- slide_win, right_end bit by bit, left_end loop reduce;
- [1, 2, 3], income=4 -> [4], [3, 4], [2, 3, 4], [1, 2, 3, 4]
- https://leetcode.com/problems/subarray-product-less-than-k
- https://leetcode.com/submissions/detail/548109082/
- EG
- SUMMA
- left_win: right_end inc bit by bit
- right_win: left_end reduce bit by bit
- https://leetcode.com/problems/find-pivot-index
- EG
- SUMMA
- method 1:
- 2_sort_arr; i_f (r), j_f (r), k_f (w); together, anything left
- method 2:
- in_place
- 2_sort_subarr; i_b (r), j_b (r), k_b (w); else_catch_everything (i over-run)
- https://leetcode.com/submissions/detail/477449924/
- https://leetcode.com/problems/merge-sorted-array
- EG
- SUMMA
- method 1:
- 2_sort_subarr; i_f (r), j_b (r), else_catch_everything
- method 2:
- 2_sort_subarr; i_b (r), j_f (r); no_else_catch_everything, so complicated
- https://leetcode.com/problems/squares-of-a-sorted-array
- EG
- SUMMA
-
- past, inject
-
- freq
- EG
- SUMMA
- no sort, hash (freq), build_from_groud
- https://practice.geeksforgeeks.org/viewSol.php?subId=ef93198b6ad4ffc74cf627d7e52294e3&pid=702382&user=figo2476
- EG
- SUMMA
- hash (met_before)
- https://practice.geeksforgeeks.org/problems/remove-duplicates3034/1#
- EG
- SUMMA
- 1 to 1, 2 hash; h_key[key] = val, h_val[val] = key
- https://leetcode.com/problems/word-pattern
- EG
- SUMMA
- EG
- SUMMA
- set (set1.size == set2.size)
- https://leetcode.com/problems/word-pattern
- EG
- SUMMA
- leader >= everything at right; max represent entire subarr
- https://practice.geeksforgeeks.org/problems/leaders-in-an-array-1587115620/1
- EG
- SUMMA
- a[i] + extra > max; max represent entire subarr
- https://leetcode.com/problems/kids-with-the-greatest-number-of-candies
- EG
- SUMMA
- next_each....; max represent entire subarr
- https://leetcode.com/submissions/detail/485237779/
- https://leetcode.com/problems/global-and-local-inversions
- EG
- SUMMA
- brute_force
- each_char == level_of_filter
- (1) no update pool (2) update pool (once outloop)*; (3) update pool (inner loop);
- arr[each_char][result]
- e.g. ["abc", "def"] -> 2D_arr
- https://leetcode.com/problems/search-suggestions-system
- EG
- SUMMA
- brute_force
- s.startsWith (prefix)
- (1) no update pool* (2) update pool (once outloop); (3) update pool (inner loop);
- arr[each_char][result]
- e.g. ["abc", "def"] -> 2D_arr
- https://leetcode.com/problems/search-suggestions-system
- EG
- SUMMA
- ind causes l, r to bound; use left (binary search)
- products[l] < target (*) VS products[l] <= target
- https://leetcode.com/problems/search-suggestions-system
- EG
- SUMMA
- (1)
- l = 0 (stable)
- r = len; r = len-1; (outbound / inbound)
- (2)
- loop(l < r); loop(l <= r) (outbound / inbound)
- (3)
- ind = (l+r)/2; ind = l + (r-l)/2; (!matter / !matter)
- (4)
- l = ind+1 (stable)
- r = ind; r = ind-1 (include / exclude)
- method 1:
- outbound -> outbound -> !mastter -> include
- method 2:
- inbound -> inbound -> !mastter -> exclude
- https://leetcode.com/submissions/detail/475070091/
- https://leetcode.com/problems/search-insert-position
- EG
- SUMMA
- method 1:
- ind*ind is square (binary search)
- method 2:
- natural bottom up
- https://leetcode.com/problems/sqrtx
- EG
- SUMMA
- method 1:
- ind*ind is square (binary search)
- method 2:
- natural bottom up
- https://leetcode.com/problems/valid-perfect-square
- EG
- SUMMA
- method 1:
- [g, g, g, g, b, b, b] -> left most vs right most
- method 2:
- natural bottom up
- https://leetcode.com/problems/first-bad-version/discuss/71386/An-clear-way-to-use-binary-search
- https://leetcode.com/problems/first-bad-version
- EG
- SUMMA
- ~= first bad version
- https://leetcode.com/problems/guess-number-higher-or-lower/
- EG
- SUMMA
- ele_i = tar - ns[i] (pool of ele, binary search)
- bs(arr, l_smaller, r, tar)
- https://leetcode.com/submissions/detail/538754691/
- https://leetcode.com/problems/two-sum-ii-input-array-is-sorted
- EG
- SUMMA
- ele_i = tar - ns[i] (pool of ele, binary search)
- bs(arr, l_smaller, r, tar)
- https://leetcode.com/submissions/detail/538754691/
- https://leetcode.com/problems/two-sum-ii-input-array-is-sorted
- EG
- SUMMA
- ns1_unique (arr1 binary_search arr2)
- https://leetcode.com/submissions/detail/538876175/
- https://leetcode.com/problems/intersection-of-two-arrays/
- EG
- SUMMA
- method 1
- brute_force, binary search left most
- https://leetcode.com/submissions/detail/539892078/
- https://leetcode.com/problems/intersection-of-two-arrays-ii/
- EG
- SUMMA
- a[ind] > tar
- a[ind] < tar
- https://leetcode.com/submissions/detail/540921981/
- https://leetcode.com/problems/search-in-rotated-sorted-array/
- EG
- SUMMA
- step = 10;
- while(true), binary search, !found, step*2
- https://stackoverflow.com/questions/16513429/binary-search-on-unknown-size-array
- EG
- SUMMA
- [0, 0, 2, 2, 1, 1] -> build_from_ground (hash) -> [0, 0, 1, 1, 2, 2] (limited_ele)
- https://practice.geeksforgeeks.org/viewSol.php?subId=ef93198b6ad4ffc74cf627d7e52294e3&pid=702382&user=figo2476
- https://practice.geeksforgeeks.org/problems/sort-an-array-of-0s-1s-and-2s4231
- EG
- SUMMA
- burte_force; single_ele is subarr, extend is subarr; sum up and down
- https://leetcode.com/submissions/detail/541256024/
- https://leetcode.com/problems/subarray-sum-equals-k
- EG
- SUMMA
- 2_diff: pre_sum_2 - pre_sum_1 = tar
- 2_sum: ele_2 + ele_1 = tar
- hash (direct_prev) -> hash (related_prev)
- https://leetcode.com/submissions/detail/541256024/
- https://leetcode.com/problems/subarray-sum-equals-k
- EG
- SUMMA
- 2_sum: ele_2 + ele_1 = tar
- hash (direct_prev) -> hash (related_prev)
- https://leetcode.com/problems/two-sum
- EG
- SUMMA
- brute_force
- i_stable, j_loop
- https://leetcode.com/problems/two-sum
- EG
- SUMMA
- 2_sum: ele_2 + ele_1 = tar
- hash (direct_prev) -> hash (related_prev)
- https://leetcode.com/problems/two-sum
- EG
- SUMMA
- i_start, j_end + skip_loop (remove repeated)
- https://www.geeksforgeeks.org/count-distinct-pairs-with-given-sum/
- https://hjweds.gitbooks.io/leetcode/content/two-pointers/2-sum-all-pair-ii.html
2sum (repeated, find distinct pair); a+a = tar (a once) OR a+b = tar (a many times, but b once), hash (freq)
- EG
- SUMMA
- a+a = tar (a once) OR a+b = tar (a many times, but b once), hash (freq)
- https://www.geeksforgeeks.org/count-distinct-pairs-with-given-sum/
- https://hjweds.gitbooks.io/leetcode/content/two-pointers/2-sum-all-pair-ii.html
- EG
- SUMMA
- 2pt, i and j meet; max
- https://gist.github.com/yitonghe00/76a5f3034c9c81ebf8be3433e6865eae
- https://leetcode.com/problems/two-sum-less-than-k/
- EG
- SUMMA
- all_the_way vs hash(ind = presum_diff); hash(set 1/+1)
- why map(0, 1)?
- all_the_way
- code?
- all_the_way (count++)
- hash(presum_diff) (count++)
- hash (freq)
- https://leetcode.com/submissions/detail/541397103/
- https://leetcode.com/problems/subarray-sum-equals-k
- EG
- SUMMA
- all_the_way vs hash(ind = presum_diff); hash (posi)
- code?
- all_the_way (max)
- hash(presum_diff) (max)
- hash(posi)
- https://leetcode.com/problems/maximum-size-subarray-sum-equals-k
- https://cheonhyangzhang.gitbooks.io/leetcode-solutions/content/325-maximum-size-subarray-sum-equals-k.html
- EG
- SUMMA
- all_the_way vs hash(ind = presum%mod); hash (set 1/+1)
- ind < 0?
- ind = presum%mod < 0, + mod
- https://leetcode.com/submissions/detail/542285893/
- https://leetcode.com/problems/subarray-sums-divisible-by-k
- EG
- SUMMA
- all_the_way vs hash(ind = presum%mod); hash(posi)
- overwritten?
- [1, 1, 0_will_be_overwritten] -> presum: [1, 2_overwritten, 2_overwritten]
- mod?
- mod <-> mutiply
- mod control ind
- ind = presum%mod?
- s2%mod - s1%mod = 0 (met again) --> (s2-s1)%mod = 0
- why distance > 1?
- why map(0, -1_posi)?
- all_the_way: len = 3_ind + 1; -1_posi
- presum diff: 3_ind - 1_ind = 2_len
- https://leetcode.com/submissions/detail/545430683/
- https://leetcode.com/problems/continuous-subarray-sum
[3, 1, 2, 5, 3], k = 3_odd -> [1, 1, 0, 1, 1], k = 3; all_the_way vs hash(ind = presum_diff); hash(set 1/+1)
- EG
- SUMMA
- all_the_way vs hash(ind = presum diff); hash(set 1/+1)
- [3, 1, 2, 5, 3] -> [1, 1, 0, 1, 1]_even_odd
- https://leetcode.com/problems/count-number-of-nice-subarrays
- EG
- SUMMA
- all_the_way vs hash(ind = presum diff); hash(set 1/+1)
- https://leetcode.com/problems/binary-subarrays-with-sum/
other lists: https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E7%9B%AE%E5%BD%95.md
- EG
- SUMMA
- log identifier + log content; without log identifier + log content;
- https://leetcode.com/submissions/detail/503865437/
- https://leetcode.com/problems/reorder-data-in-log-files/
- EG
- SUMMA
- ab, ba, ba vs ab; return ba-ab; diff better sort num
- https://leetcode.com/submissions/detail/477886109/
- https://leetcode.com/problems/largest-number
- https://practice.geeksforgeeks.org/problems/largest-number-formed-from-an-array1117/1
- EG
- code: [[apple, apple], [orange, *, orange]] -> [[a, a], [o, *, o]] -> substrs
- cart: [appple, apple, x, x, orange, apple, orange] -> [a, a, x, x, o, o, o] -> sentense
- SUMMA
- chars in substr (order); substrs in sentense (order, gap)
- slide (exhaust), then extend (match); match good; !match, reset substr, next_char_sentence
- see my amazon code
- https://leetcode.com/discuss/interview-question/1002811/Amazon-or-OA-2021-or-Fresh-Promotion
- EG
- code: [[apple, apple], [orange, *, orange]] -> [[a, a], [o, *, o]] -> substrs
- cart: [appple, apple, x, x, orange, apple, orange] -> [a, a, x, x, o, o, o] -> sentense
- SUMMA
- chars in substr (order); substrs in sentense (order, gap)
- slide (exhaust), then extend (match); match good; !match, reset substr, next_char_sentence
- see my amazon code
- https://leetcode.com/discuss/interview-question/1002811/Amazon-or-OA-2021-or-Fresh-Promotion
- EG
- SUMMA
- slide (exhaust), then extend (match); match good; !match, reset substr, next_char_sentence
- https://leetcode.com/problems/implement-strstr
- EG
- SUMMA
- is myself part of others (include self)?
- https://leetcode.com/problems/string-matching-in-an-array
- EG
- SUMMA
- (1) 1 on 1 exact_match (2) extend_match (look_back) (3) false
- https://leetcode.com/problems/long-pressed-name
- EG
- SUMMA
- method 1:
- look_forward; partition, i, i+1, partition
- sub(0, i), i, i+1, sub(i+2)
- method 2:
- look_backward; partition, i-1, i, partition
- sub(0, i-1), i-1, i, sub(i+1)
- https://xiaoguan.gitbooks.io/leetcode/content/LeetCode/293-flip-game-easy.html
- EG
- SUMMA
- method 1:
- leading char (same_char), continue (leading_char), reset (diff_char) (1 loop)
- method 2:
- skip loop (2 loop, but underneath 1 loop)
- https://leetcode.com/problems/consecutive-characters
- EG
- SUMMA
- continue (!part_sum), reset (part_sum)
- https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum
- EG
- A absent, L late, P present;
- SUMMA
- count_A, count_L
- single_loop, continue (LLL), reset (LLA)
- https://leetcode.com/submissions/detail/507769749/
- https://leetcode.com/problems/student-attendance-record-i
- EG
- SUMMA
- continue (inc), reset (desc)
- https://leetcode.com/submissions/detail/510419128/
- https://leetcode.com/problems/longest-continuous-increasing-subsequence/
- EG
- 1 -> 1 (init);
- 1 -> 11;
- 11 -> 21;
- 21 -> 1211
- SUMMA
-
- input = say(input)
-
- continue (past vs curr), reset (past, curr, curr_tobe_past)
- https://leetcode.com/submissions/detail/507769749/
- https://leetcode.com/problems/count-and-say
- EG
- SUMMA
- method 1:
- income_ele chg internal_ele prop (odd/even); brute_force
- method 2:
- income_ele chg internal_ele prop (odd/even); precompute sum(even);
- https://leetcode.com/problems/sum-of-even-numbers-after-queries
- EG
- SUMMA
- sort, vertical_compare; direct_cancel (vertical, similar_but_diff_posi)
- https://leetcode.com/problems/valid-anagram
n = 5 -> [-2, -1, 0, 1, 2]; n = 4 -> [-2, -1, 1, 2]; direct_cancel (horizontal, similar_but_diff_posi)
- EG
- SUMMA
- x-coordinate; direct_cancel (symmetric, similar_but_diff_posi)
- https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero
- EG
- SUMMA
- s1 (small_pool), s2 (big_pool); direct_cancel (diff_pool_size, similar_but_diff_posi)
- https://leetcode.com/problems/ransom-note
- EG
- SUMMA
- unsort, hash; delay_cancel (eventuall_balance, similar_but_diff_posi)
- https://leetcode.com/problems/valid-anagram
[a, b], [c, d], [b, c] -> sort [a, b], [b, c], [c, d]; delay_cancel ([in, out], similar_but_diff_posi)
- EG
- SUMMA
- delay_cancel ([in, out], similar_but_diff_posi)
- https://leetcode.com/submissions/detail/525476821/
- https://leetcode.com/problems/destination-city
- EG
- SUMMA
- method 1:
- permutation -> any_combo -> palin? (brute_force)
- method 2:
- palin (odd) -> cancel (delay) -> 1 left
- palin (even) -> cancel (delay) -> 0 left
- https://medium.com/swlh/palindrome-permutations-9752d8e71c7f
RLLRRL -> RLLR + RL, res = 2; or RLLRRL -> RL + LR + RL, res = 3 (max); greedy_cancel (similar_but_diff_posi)
- EG
- SUMMA
- greedy_split; greedy_cancel (similar_but_diff_posi)
- sub_balance_1 (L# == R#, !order, greedy) + sub_balance_2 (...) + sub_balance_2 (...) + ... == balance_whole (...)
- https://leetcode.com/problems/split-a-string-in-balanced-strings
- EG
- SUMMA
- moving -> coordinate; hash (past)
- https://leetcode.com/problems/path-crossing
- EG
- SUMMA
- moving -> coordinate
- https://leetcode.com/problems/robot-return-to-origin
- EG
- SUMMA
- https://leetcode.com/submissions/detail/510165020/
- https://leetcode.com/problems/count-binary-substrings
- EG
- SUMMA
-
- col_1: start / end
-
- col_2: use / release resource
-
- col_3: curr_resource
- https://leetcode.com/problems/car-pooling/
- EG
- SUMMA
- treeMap (keep injecting) === loop + treeMap (static)
- https://leetcode.com/problems/my-calendar-i
- EG
- SUMMA
- intersect formular (mid 3 block); past_start < income_end && past_end > income_start
- https://leetcode.com/problems/my-calendar-i
- EG
- SUMMA
- intersect formular (top + bottom block);
- https://leetcode.com/problems/my-calendar-i
- EG
- SUMMA
- just fyi
- EG
- SUMMA
- method 1:
- 1st_booking (mem), 2nd_booking (double booking); 3 mid block
- method 2:
- treeMap (keep injecting); inject (no_matter), good_keep, bad_out
- https://leetcode.com/problems/my-calendar-i
- EG
- SUMMA
- method 1:
- 1st_booking (mem1), 2nd_booking (mem2, do_merge), 3rd_booking (tripple booking); 3 mid block
- each mem hold all income; each mem represents own state
- method 2:
- treeMap (keep injecting); inject (no_matter), good_keep, bad_out
- https://leetcode.com/problems/my-calendar-ii
- EG
- SUMMA
- method 1:
- treeMap (keep injecting);
- https://leetcode.com/problems/my-calendar-iii
- EG
- SUMMA
- treeMap (static; start/end, use/release, curr_resouce); count >= 2, bad
- https://www.programcreek.com/2014/07/leetcode-meeting-rooms-java/
- EG
- SUMMA
- treeMap (static; ....); count = max
- https://osgoodgunawan.medium.com/meeting-room-ii-in-javascript-d478690dd432
- https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/253.%20Meeting%20Rooms%20II.md
- EG
- SUMMA
- method 1:
- treeMap (keep injecting) == loop + treeMap (static);
- inject (no_matter), good_keep, bad_out
- method 2:
- prepare, then query (incoming data); fill_time_block; easier to understand
- https://leetcode.com/discuss/interview-question/613816/Google-or-Onsite-or-Meeting-Rooms-3
- see my js file in code dir (for time fill method)
- EG
- SUMMA
- treeMap (static; start/end, +/-, curr_res)
- https://practice.geeksforgeeks.org/problems/minimum-platforms-1587115620/1#
- https://practice.geeksforgeeks.org/viewSol.php?subId=a5d446a873521478733111306c0e77dd&pid=701368&user=figo2476
- EG
- SUMMA
- treeMap (static; start/end, +/-, curr_res)
- https://leetcode.com/problems/car-pooling/
- EG
- SUMMA
- overlap (become_1, with_merge)
- https://leetcode.com/problems/merge-intervals/
- https://leetcode.com/submissions/detail/520779033/
- EG
- SUMMA
- overlap (become 1, with_small)
- https://leetcode.com/submissions/detail/520798909/
- https://leetcode.com/problems/non-overlapping-intervals/
- EG
- SUMMA
- overlap (become 1, with_small, shoot_arrow)
- https://leetcode.com/submissions/detail/521275495/
- https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons
LOOnBALxBALLpOOn; h {b:3, a:3, l:3, o:3, n:3} -> h {b:3, a:3, l:3/2, o:3/2, n:1}, so 1; min is strength (min is strength)
- EG
- SUMMA
- min is max strength (whoever min)
- https://leetcode.com/problems/maximum-number-of-balloons
LOOnBALxBALLpOOn; h {b:3, a:3, l:3, o:3, n:3} -> h {b:2, a:2, l:1, o:1, n:2}, so 1; min is strength (rm_same_time)
- EG
- SUMMA
- min is max strength (batch remove)
- https://leetcode.com/problems/maximum-number-of-balloons
- A = A' + (x/2 + x/2)
- B = B' + (x/2)
- swap
- A' + (x/2) == B' + (x/2 + x/2)
- swap, then equal
- https://leetcode.com/problems/fair-candy-swap
- EG
- SUMMA
- loop ele (x, y)
- (dy / dx) == (y1 - y) / (x1 - x) (dy = y1-y0)
- dy * (x1 - x) !== dx * (y1 - y) (not straight line)
- https://leetcode.com/problems/check-if-it-is-a-straight-line
- EG
- SUMMA
- diag to hor / ver (diag cover hor / ver), then straight_line; shortest
- https://leetcode.com/problems/minimum-time-visiting-all-points
- 1 iteration, push 1 bubble to end
- if anything not sort, bubble continue
- i vs (i and res_inds);
- i vs (i+1 and res_inds);
- i vs (0 and res_inds);
- EG
- combo_sum_1, ns = [2,3,6,7], tar = 7, res = [[2,2,3],[7]]
- SUMMA
- sort_rm_dup
- bt(final_res, tmp_arr, ns_orig, curr_i, tar)
- recur_stop_check: tar_reach || tar_overconsume
- recur:
- single_loop (i vs i and res_inds)
- before_op, look_back, sort_rm_dup
- tmp_arr_new = tmp_arr.concat(ns[i]) (concat)
- bt (tar_desc) (0_repeat_entire_x; i-1_x; i_no_repeat + include_self; i+1_miss_self_x)
- https://leetcode.com/problems/combination-sum
- EG
- combo_sum_2; ns = [2,5,2,1,2], tar = 5, res = [[1,2,2], [5]];
- SUMMA
- sort_rm_dup
- bt(final_res, tmp_arr, ns_orig, curr_i, tar)
- recur_stop_check: tar_reach || tar_overconsume
- recur:
- single_loop (i vs i+1 and res_inds)
- tmp_arr_new = tmp_arr.concat(ns[i]) (concat)
- bt_recur_abstract_return(tar_desc) (0_repeat_entire_x; i-1_x; i_repeat_self_x; i+1_avoid_self + res)
- https://leetcode.com/problems/combination-sum-ii
- EG
- combo_sum_3; ns = [1, 2, 3, ... 9], k_len = 3, tar = 7, res = [[1,2,4];
- SUMMA
- sort_rm_dup
- ns_orig = [1, 2, 3, 4, 5, 6, 7, 8, 9] (new_part)
- bt(final_res, tmp_arr, ns_orig, curr_i, tar)
- recur_stop_check: tar_reach + len_reach || tar_overconsume or len_overconsume
- recur:
- single_loop (i vs i+1 and res_inds)
- tmp_arr_new = tmp_arr.concat(ns[i]) (concat)
- bt_recur_abstract_return(tar_desc) (0_repeat_entire_x; i-1_x; i_repeat_self_x; i+1_avoid_self + res)
- https://leetcode.com/problems/combination-sum-iii