About repo

In this repo you can find:

• Leetcode
  • Blind 75 explanations and solutions
  • Some other leetcode solutions
• Solutions and (rarely) explanations for yandex 2025 autumn contest
• My implementations of basic data sctructures (at 2025-01-03 only list is implemented)

Leetcode

My leetcode profile.

Top 75 LeetCode Questions

• Array

  • Two Sum
  • Best Time to Buy and Sell Stock
  • Contains Duplicate
  • Product of Array Except Self
  • Maximum Subarray
  • Maximum Product Subarray
    • time - O(N), space - (1):
      • Main idea: iterate through array and update Max and Min possible product, which includes current value. Edge case: if val == 0, then Max=1,Min=1
      • Step by step:
        • initialize Max, Min and res

          int Max = 1, Min = 1, res = INT_MIN;

        • iterate through nums:

          for(const int& val : nums) {

          • if val is 0, then set Min=1 and Max=1, BUT DO NOT update res

            if (val == 0) {
                Max = 1;
                Min = 1;
                res = max(val, res);
            } 

          • else update Max and Min in such way that they include val. then update the res

            else {
                int NewMax = max(Max * val, Min * val);
                NewMax = max(NewMax, val);
                int NewMin = min(Min * val, Max * val);
                NewMin = min(NewMin, val);
                Max = NewMax;
                Min = NewMin;
                res = max(Max, res);
            }

        • return res
  • Find Minimum in Rotated Sorted Array
  • Search in Rotated Sorted Array
  • 3Sum
    • this solution is not efficient at all (beats 12% runtime and 13% memory), i will probably come back to this problem later
    • time - O(N^2 Log N), space - O(N)
      • sort nums
      • remove duplicates from nums:
        • each value can be repeated not more than 3 times
        • ex. [0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,-1,-1,-1] -> [0,0,0,1,1,1,-1,-1,-1]
      • res_set = set()
      • iterate first_val_inx (0 ... len(nums))
        • iterate second_val_inx (first_val_inx+1 ... len(nums))
          • target = -(nums[first_val_inx] + nums[second_val_inx])
          • find target using binary search
          • if target is found:
            • add triplet to res_set
  • Container With Most Water

• Binary

  • Sum of Two Integers
    • time - O(1), space - O(1):
      • for 0b01 (1) and 0b10 (2) we can just use bitwise OR to get their sum :

        0b01 OR
        0b10 =
        0b11 (= 3)
        

      • however, if at least one bit is enabled both in a and b, we can't use bitwise OR, because in this case we loose bits. For example, it doesn't work with 0b101 (5) and 0b001 (1), which sum should be 6:

        0b101 OR
        0b001 =
        0b101 (= 5)
        

        • 5 isn't correct answer
      • so, to solve this problem, we need to rewrite a and b in such way that their sum gives same sum but no same bits enabled. e.g.0b010 (2) and 0b100 (4), which sum is also 6:

        0b010 OR
        0b100 =
        0b110 (= 6)
        

        • now we got correct answer
      • but how can we modify a and b in such way that they don't have same enabled bits?
        • while a and b have at least one common enabled bit

          while ((a & b) != 0) {

        • we get bits that are enabled only in a or only in b

          int tmp = a ^ b;

        • we get common enabled bits and move them left (0b1 + 0b1 = 0b10)

          b = (a & b) << 1;

        • and don't forget to update a:

          a = tmp;

      • and when a and b don't have common enabled bits, we can return the answer:

        return a | b;

  • Number of 1 Bits
  • Counting Bits
  • Missing Number
    • Actually used brute force approach: just sorted array and iterated until found a gap.
  • Reverse Bits
    • Don't forget that to set last bit of 32-bits signed integer you need to do num |= 1 << 31, NOT num |= 1 << 32. And to set first bit -> num |= 1 << 0.

• Dynamic Programming

  • Climbing Stairs
  • Coin Change
    • time - O(amount * coins.length), space - O(amount)
      • create best_qty = [amount+1] * (amount+1)
      • best_qty[0] = 0
      • iterate cur_amount in range 0..amount
        • iterate through coins
          • best_qty[cur_amount] = min(best_qty[cur_amount], best_qty[cur_amount-coin] + 1)
      • return best_qty[amount] > amount ? -1 : best_qty[amount];
  • Longest Increasing Subsequence
    • O(n^2) Bottom Up:
      • dp[i] = longest combination for nums[i:]
        • to get longest combination for nums[i:] we iterate through dp[:i+1] and nums[i:] to get max dp for num that is bigger than current (if nums[j] > curr then dp[i] = max(dp[i], 1+dp[j]))
      • e.g. we have nums=[1,10,3,1,2]
        • i = 4 (nums[i]=2)
          • dp[4] = 1
        • i = 3 (nums[i]=1)
          • dp[3] = 2 (because nums[3] < nums[4])
        • i = 2 (nums[i]=3)
          • dp[2] = 2
        • i = 1 (nums[i]=10)
          • dp[1] = 1 (because nums[i+1:] are bigger than nums[i])
        • i = 0 (nums[i]=1)
          • dp[0] = 2
      • and then we return max(dp)
    • time - O(N log N), space - O(N)
      • Binary Search solution
  • Longest Common Subsequence
    • O(n*m) Bottom Up:
      • Make matrix n x m. Find best solution for text1[n-1:] and text2[m-1:], then to text1[n-2:] and text2[m-1:], ...
      • If text1[a] == text2[b], then best solution for text1[a:] and text2[b:] is equal to 1 + best solution for text1[a+1:] and text2[b+1:]
      • Otherwise, the best solution is MAX(best for text1[a+1:] and text2[b:], best for text1[a:] and text2[b+1:])
  • Word Break
    • O(n*m*n) Top Down:
      • If we know that we can reach s[i] with words from wordDict, then we find all s[n] (n>i) that we can reach with words from wordDict and set dp[n]=true
      • Make dp[len(s)+1]. Set dp[0]=0.
      • Iterate i in range(0, len(s))
        • if dp[i] == true
          • iterate through wordDict and if s[i:].startswith(wordDict[j]), then set dp[i + len(wordDict[j])] = true
      • Return dp[len(s)+1]
    • O(n*m*n) Bottom Up:
      • If s[i].startswith(wordDict[j]) and dp[i+len(wordDict[j])] == true, then dp[i] == true
  • Combination Sum IV
    • O(Target*N) Top Down:
      • Step by step find best solution for 0..Target (CurrentTarget) and save it to dp Map
      • So, to calculate dp[i] you can use previous values dp[i] += dp.get(CurrentTarget - Num, 0) for Num in Nums
  • House Robber
    • O(n): Overall approach:
      1. dp = nums
      2. for i in range (len(nums) + 2)
         1. dp[i] += max(dp[i-2], dp[i-3])
      3. result is dp[-1]
  • House Robber II
    • O(n):
      • Use previous problem to solve this one
      • Result = max(original_rob(Nums[1:]), original_rob(Nums[:-1]))
  • Decode Ways
    • O(n):
      • pseudo code:

        for i in range(0, len(str)): # this is general case (think about first letters)
            dp[i] += dp[i-2] if i >= 2 and 1 <= int(s[i-1] + s[i]) <= 26 else 0
            dp[i] += dp[i-1] if s[i] != '0' else 0

      • idea:
        • if s[i] != '0', then it can represent letter, so to dp[i] we can add all variants of encoding s[:i] (because there is one way to get from s[i-1] to s[i])
        • if 1 <= int(s[i-1] + s[i]) <= 26, then current and previous numbers can represent letters, so to dp[i] we can add all variants of encoding s[:i-1] (because there is one way to get from s[i-2] to s[i])
  • Unique Paths
    • O(n * m):
      • pseudo code:

        for M in range(m):
          for N in range(n):
            dp[N][M] = dp[n-1][m] + dp[n][m-1]
        return [n-1][m-1]

      • idea:
        • for every cell in first row number of paths is equal to one, so we make list [1] * n
        • for next rows: number of paths is equal to number of paths for upper cell + number of paths for left cell
        • return number of paths for last cell
  • Jump Game
    • O(n):
      • idea:
        • while iterating through array, update max_inx value which stores maximum index you can reach. if i > max_inx, then return false. if max_inx >= len(nums)-1, return true.

• Graph

  • Clone Graph
    • If s == NULL, then just return NULL
    • Make struct Node* arr[101] to store all processed nodes
    • Then iterate through neighbors nodes starting from s (DFS):
      • If node is already in arr, then return it
      • Otherwise, add node to arr and start to iterate though its neighbours...
  • Course Schedule
    • Make a dict PreMap and use course for key and list of prerequisites for value
    • Make set visited
    • dfs algorithm:
      • If course in visited, then return False (because that means that we are in loop which means that to finish course you need to finish this course before which is impossible)
      • If course in PreMap and prerequisites is empty list, then return True
      • Add course to visited and run dfs through each prerequisites of current course.
        • If at least one returns False -> also return False
      • Remove current course from visited
      • Set PreMap[course]=[] (we already checked that course, so no need to check it again)
    • Run dfs for i in range(0, numCourses)
  • Pacific Atlantic Water Flow
    • Start from Pacific borders and iterate like this:
      • If r not out of boundaries AND c not out of boundaries AND (r,c) not in CanReachPacific AND heights[r][c] <= heights[prev_r][prev_c]
        • Add (r,c) to CanReachPacific
        • Iterate through (r+1,c)
        • Iterate through (r-1,c)
        • Iterate through (r,c+1)
        • Iterate through (r,c-1)
    • Repeat same thing with Atlantic
    • Find CanReachPacific and CanReachAtlantic intersections and return them
  • Number of Islands
    • with all r (0..gridSize) and c (0..gridColSize) combinations:
      • if grid[r][c] == 1 ->
        • res += 1
        • Set all cells of island to zero, so, we won't explore this island second time.
  • Longest Consecutive Sequence
    • Make set numsSet with nums
    • Iterate through numsSet and find begginging of sequence
      • Set length to zero
      • Start while loop (while num+length in numsSet)
        • length++;
      • Compare best length with this length
      • Return best length
  • Alien Dictionary (Premium)
    • Make a dict[char: set], where set includes chars bigger than char. e.g. if ["ab", "ac"], then dict should be {"b": {"c"}}
    • Use post-order DFS to get the result
      • Iterate through nodes until found graph with no further nodes. Add it to res. Then add its parents to res, then their parents...
      • After iteration is done, reverse the result list
      • IMPORTANT NOTE: if loop if found, then algorithm should return ""
    • return reversed result list
  • Graph Valid Tree (Premium)
    • There are 2 conditions for valid Tree:
      • Graph should be interconnected
      • Graph should not contain loops
    • Make dict adj for each edge in edges:
      • adj[edge[0]].append(edge[1])
      • adj[edge[1]].append(edge[0])
    • make visited set
    • Dfs:
      • if element in visited: return False (loop detection!)
      • visited.add(element)
      • iterate through neighbors (through adj[element])
        • if neighbor != prev_dfs_val
          • Explanation of "neighbor != prev_dfs_val": prev_dfs_val (the edge from which we came to current edge) is in visited, so, if we run dfs for prev_dfs_val again, we will get false-positive loop detection and return False
          • if (dfs(element=neighbor, prev_dfs_val=element, visited, nodes) == False): return False
      • return True
    • Note: the main function should call dfs only once, because if graph is interconnected, then you can find ALL edges starting from any edge in graph. For example:

      • Node1 - Node2 - Node4
                      - Node5
              - Node3
        # from any node i can get to any node. For example, let's start from Node5:
          - Node5->Node4->Node2->Node1->Node3
        

      • Node1 - Node2 - Node4
                      - Node5
              - Node3
        
        Node7 - Node8
        # we never can get to Node3 if we start from Node7 or Node8, 
        

    • return dfs(0, -1, visited, nodes) && n == len(visited)
    • Explanation: during dfs we find loops (if element was visited twice -> return False) and by n == len(visited) we check that graph is interconnected (if graph isn't interconnected -> dfs won't visit all edges)
  • Number of Connected Components in an Undirected Graph (Premium)
    • Very similar to Number of Islands
    • O(V + E) (V - num of vertices, E - num of edges)
      • Important note! The node may NOT BE PRESENT IN edges. So, this situation is possible: edges=[0,1], n = 4, it can be illustrated like this:

        Node0 - Node1
        
        Node2
        
        Node3
        
        Node4
        

      • So, adj={i: [] for i in range(n)}
      • Then we fill adj. for edge in edges:
        • adj[edge[0]].append(edge[1])
        • adj[edge[1]].append(edge[0])
      • DFS algorithm (args: int i, dict[int,list[int]] adj):
        • Explanation: when we get i, we delete all nodes connected with i
        • If i not in adj (this node was already explored)
        • neighbors = adj.pop(i)
        • for neighbor in neighbors:
          • DFS(neighbor, adj)
      • res = 0
      • for i in range(0, n):
        • if i in adj: (if this group of connected nodes wasn't explored)
          • res+=1
          • DFS(i, adj) (remove all connected nodes)
      • return res

• Interval

  • Insert Interval
    • O(n):

      • My explanation on leetcode

      • Input interval consists of 3 parts (but sometimes not all parts are present):

        	Part1	Part2	Part3
        Condition	Intervals[i][1] < NewInterval[0]	NOT Part1 AND NOT Part3	NewInterval[1] < Intervals[i][0]
        Action	res.add(Intervals[i])	NewInterval = [min(NewInterval[0], Interval[i][0]), max(NewInterval[1], Interval[i][1])]	res.add(NewInterval), RETURN res + Intervals[i:]
        Explanation	We need all intervals that are smaller than NewInterval, so add all of them	We merge overlapping intervals	We insert NewInterval just before the part where all intervals are bigger than NewInterval

    • Possible optimizations:
      • It is possible to solve this problem in-place (not create new list, but update input list). It would be O(1) space complexity
      • Also, with binary search it is possible to find all three parts. It would be O(log n) time complexity.
  • Merge Intervals
    • time - O(Nlogn), space - O(N)
      • Sort input intervals
      • Initialize integers Start, End = interval[0][1], interval[0][1]
      • Iterate through intervals:
        • if intervals[i][0] <= Start -> End = MAX(End, intervals[i])
        • else -> add [Start, End] to res, set Start, End = intervals[i][0], intervals[i][1]
      • add [Start, End] to res
      • return res
  • Non-overlapping Intervals
    • time - O(N log N), space - O(1)
      • Sort input intervals
      • Save prev_end = intervals[0][1]
      • Iterate through sorted intervals[1:]:
        • if intervals[i][0] >= prev_end (if doesn't overlap with prev interval):
          • prev_end = intervals[i][1]
        • else (interval overlaps with prev interval):
          • res += 1 (need to remove some interval in any case)
          • prev_end = min(prev_end, intervals[i][1]) (save interval with smallest prev_end, because it will overlap with smaller number of intervals)
  • Meeting Rooms (Premium)
    • time - O(N log N), space - O(1):
      • Sort intervals by start
      • Iterate through intervals
        • If prev interval end is bigger than current interval start -> return false
      • return true
  • Meeting Rooms II (Premium)
    • time - O(N log N), space - O(n):
      • Sort intervals by start
      • Create empty list last_elements to store the end of last meeting for day. Keep last_elements sorted
      • Iterate through intervals:
        • If intervals[i].start is smaller than smallest element in last_elements:
          • We can't put this meeting in existing days. We need one more
          • We add intervals[i].end to last_elements. Keep last_elements sorted!
        • Else:
          • We can put this meeting in existing day
          • We move the end of last meeting for day:
            • Remove end of last meeting for this day.
            • We add intervals[i].end to last_elements. Keep last_elements sorted!
    • For example, we have intervals [(25,579),(218,918),(1281,1307),(623,1320),(685,1353),(1308,1358)]:

      i = 0, intervals[i].start=25, intervals[i].end=579, last_elements: # we add end of first meeting:
      
      i = 1, intervals[i].start=218, intervals[i].end=918, last_elements: 579  # because of intervals[i] starts before 579, we need one day more:
      
      i = 2, intervals[i].start=623, intervals[i].end=1320, last_elements: 579, 918  # We can schedule meeting for existing day which last meeting ends at 579
              index to delete = 0
      
      i = 3, intervals[i].start=685, intervals[i].end=1353, last_elements: 918, 1320
      
      i = 4, intervals[i].start=1281, intervals[i].end=1307, last_elements: 918, 1320, 1353
              index to delete = 0
      
      i = 5, intervals[i].start=1308, intervals[i].end=1358, last_elements: 1307, 1320, 1353
              index to delete = 0
      
      

• Linked List

  • Reverse Linked List
    • Each value of reversed list node is value of head, each next - previously accumulated reversed list
  • Detect Cycle in a Linked List
    • time - O(N), space - O(N):
      • find duplicates by set
  • Merge Two Sorted Lists
  • Merge K Sorted Lists
    • time - O(k log k), space - O(k):
      • Note: in C++ priority_queue data structure should be used for efficiency
      • Filter out all null values from lists
      • Sort all nodes in lists (if priority_queue is used, then sort in descending order) and save them to min_heap
      • While lists is not empty:
        • to last node of res add smallest element of min_heap
        • remove smallest element of min_heap
        • add next node of removed element if next node is not null
      • return res
  • Remove Nth Node From End of List
    • time - O(N), space - O(N):
      1. save all of nodes in array
      2. get the nodeToRemove (arr[index_of_last_node - (n - 1)])
      3. get the nodeToUpdate (arr[index_of_last_node - (n - 1) - 1])
      4. set nodeToUpdate->next = nodeToRemove->next
      • but there is also EDGE CASE: if nodeToRemove is head, then we just should return next of the head
  • Reorder List
    • time - O(N), space - O(1):
      • Get the first node of second half
      • Reverse second half
      • Iterate through first and second half to update nexts

• Matrix

  • Set Matrix Zeroes

    • time - O(n*m), space - O(1)
      • use first row and first col to save if the row or the col should be set to 0

  • Spiral Matrix

    • time - O(n*m), space - O(n*m)
      • add first row of matrix to spiral and delete first row
      • add right col of matrix to spiral and delete right col
      • add last row of matrix to spiral and delete last row
      • add left col of matrix to spiral and delete left col

  • Rotate Image

    • time - O(N^2), space - O(1)
      • Process each layer one by one
        • Process each val in layer:
          • save top val
          • top <- leftc
          • left <- bottom
          • bottom <- right
          • right <- top

  • Word Search

    • time - (r * c * l^4) , space - (r * c)
      • Use dfs
        • if r or c is out of boundaries -> return false
        • if r;c inside current path -> return false
        • if board[r][c] != word[word_ind] -> return false
        • if word_ind == word.len() - 1 -> return true
        • add r;c coordinate to path
        • explore neighbors using dfs. if one of calls returns true -> return true
        • remove r;c from path
      • iterate through whole board using dfs, until true
      • if none returned true -> return false

• String

  • Longest Substring Without Repeating Characters
    • note: i solved the problem using C++ and C. My C solution has more efficient algorithm. Here I describe algorithm I applied for C solution.
    • BE CAUTIOUS: in my first implementation i made mistake - i did not consider case when one substring can be part of two different substrings. For example in word "mewmkz" the substring "ewm" can be part of "mewm" and part of "ewmkz", however, "ewmkz" is bigger.
    • time - O(N), space - O(1):
      • create array chars = [-1] * 128 to store indexes of last occurances of chars
      • left = 0
      • maxLen = 0
      • for right in range(len(s)):
        • cur_char = s[right]
        • if chars[cur_char] >= left (if cur_char is between left and right -> it is inside current word)
          • since we don't need char duplicates, we need to find biggest substring of current substring which DOES NOT include cur_char
          • left = chars[cur_char] + 1 (move left to first char after last occurance of cur_char)
        • maxLen = max(maxLen, right - left + 1)
        • char[cur_char] = right (save last occurance of char)
      • return maxLen
  • Longest Repeating Character Replacement
    • *time - O(len(s)26), space - O(26)
      • create set all_chars with all unique chars of s
      • iterate through each char in all_chars:
        • using slow and fast pointer find best solution for char
      • return biggest solution
  • Minimum Window Substring
    • Save number of each letter in t
    • Iterate through s:
      • save last usage of char s[i]
      • if enough chars for t:
        • according to last usages of chars calculate len of current window
        • if needed -> update best len of window
  • Valid Anagram
  • Group Anagrams
    • time - O(N log(N) + N * M log(M)), space - O(N * M) (N - len of strs, M - len of strs[i])
      • Sort every string in strs
      • Sort strs
      • If strs[i] == strs[i-1], then they are in same group
  • Valid Parentheses
  • Valid Palindrome
    • time - O(N), space - O(1)
      • create left and right pointers
      • move pointers to center, but don't forget to ignore non-alphanumeric chars and convert into lowercase before comparing
  • Longest Palindromic Substring
    • time - O(N^2), space - O(1)
      • There are 2 types of palindromes: odd ("zaz") or even ("issi) length
      • For every point in s try to create odd and even palindrome.
        • If s[l] == s[r] -> res++, and then:
          • save best len and value of left pointer (right pointer can be calculated by best len and best left)
          • expand palindrome (l--, r++)
          • repeat
  • Palindromic Substrings
    • time - O(N^2), space - O(1)
      • There are 2 types of palindromes: odd ("zaz") or even ("issi) length
      • For every point in s try to create odd and even palindrome.
        • If s[l] == s[r] -> res++, and then expand palindrome (l--, r++) and repeat
  • Encode and Decode Strings (Premium)
    • time - O(N), space - O(N)
      • use this notation:
        • len of word + # + word
        • len of word1 + # + word1
      • e.g. 2#ee4#jaja

• Tree

  • Maximum Depth of Binary Tree
  • Same Tree
    • time - O(N), space - O(N)
      • use dfs:
        • if p or q is null && p != q, then return false
        • else return p->val == q->val && dfs(q->left, p->left) && dfs(q->right, p->right)
  • Invert Binary Tree
  • Binary Tree Maximum Path Sum
    • time - O(N), space - O(N)
      • concept:
        • dfs(node):
          • update res if one of these vals is bigger than res:
            • node
            • left + node + right # NOTE that dfs can't return left + node + right, because parent + node + node.left + node.right is impossible
            • left + node
            • node + right
          • return best(node, left + node, right + node)
      • DON'T FORGET ABOUT CASE [-3]. I recommend to set initial res to root->val
  • Binary Tree Level Order Traversal
    • time - O(N), space - O(N)
      • def traverse(node, curr_depth):
        • add node->val to res[curr_depth]
        • traverse(node->left)
        • traverse(node->right)
  • Serialize and Deserialize Binary Tree
    • time - O(N), space - O(N)
      • serialization:
        • BFS:
          • write all vals of last row to res
          • clear last row of nodes
          • save all non-null lefts and rights as last row
      • deserialization:
        • BFS:
          • keep last row of nodes
          • update theirs lefts and rights of last row of nodex
          • clear last row of nodes
          • add lefts and rights
  • Subtree of Another Tree
    • Not very efficient solution, there should be smth better. Runtime - beats 6%, Memory - 93%
    • time - O(N * M), space - O(N * M)
      • 2 funcs:
        • compare
          • if root == subRoot && compare(root->left, subRoot->left) && compare(root->right, subRoot->right) -> return true
          • if root or subRoot is Null -> stop and don't call next compare
        • explore
          • if root == subRoot -> compare
          • if explore(root->left, subRoot) || explore(root->right, subRoot) -> return true
  • Construct Binary Tree from Preorder and Inorder Traversal
    • time - O(N), space - O(1)
      • create dict mapping where keys are values and values are keys of elements from inorder
        • inorder = [4,2,1] -> mapping = {4:0, 2:1, 1:2}
      • preorderIndex = 0
      • recurs func(start, end):
        • if start > end
          • return null
        • rootVal = preorder[preorderIndex]
        • preorderIndex += 1 (we move further and further)
        • mid = mapping[inorder[rootVal]]
        • root = Node(rootVal)
        • root->left = recurs(start, mid)
        • root->right = recurs(mid + 1, end)
      • return recurs(0, len(inorder))
  • Validate Binary Search Tree
    • time - O(N), memory - O(N):
      • for each node there is a minimum and maximum possible value, which depends on parents of node
      • e.g. [5,3,10,null,8,null,null]
        1. OK for root, because 5 is inside boundaries (-inf, +inf). then, for left child max possible val is 4, for right child minimum possible val is 6
        2. OK for left child of root, because 3 is inside boundaries (-inf, 4]. for left child max possible val is 2, min possible val is -inf, for right child max possible val is 4, min possible val is 4
        3. OK for right child of root, because 10 is inside boundaries [6, +inf)
        4. NOT OK for root->left->right, because 8 is not inside boundaries [4, 4]
  • Kth Smallest Element in a BST
    • time - O(N), space - O(k)
      • create priority_queue<int, vector<int>, greater<int>> (this type of queue returns vals in sorted order)
      • we add all nodes' vals to this queue
      • get kth smallest element using queue
  • Lowest Common Ancestor of a BST
    • time - O(height), space - O(height):
      • if (p->val > q->val)
        • swap(p, q)
      • lowestCommonAncestor(root, p, q)
        • if node->val is smaller than p (smallest val) and node->right != nullptr
          • node->right is also ancestor and it should be explored
          • lowestCommonAncestor(node->right, p, q)
        • if node->val is bigger than q (biggest val) and node->left != nullptr
          • node->left is also ancestor and it should be explored
          • lowestCommonAncestor(node->left, p, q)
        • else
          • node->left and node-right are not ancestors and should not be explored
          • return root
  • Implement Trie (Prefix Tree)
    • time - O(N), space - O(NL)
      • Each Trie should have:
        • Children: dict[char, Trie] = {}
        • IsEnd: bool = false
      • insert
        • we need pointer to current Trie and pointer to iterate through word

          int p = 0;
          Trie *cur = this;

        • then iterate through all chars in word

          while (p < word.size()) {

          • if cur was never continued by word[p] -> create corresponding Trie

            if ( cur->Children.find(word[p]) == cur->Children.end() ) {
                cur->Children[word[p]] = new Trie();
            }

          • update pointers:

            cur = (cur->Children[word[p]]);
            p++;

        • save that this Trie is the end of the word

          cur->IsEnd = true;

      • search
        • search is almost the same as insert, but
          • if cur never was continued by word[p] -> return false;

            if ( cur->Children.find(word[p]) == cur->Children.end() ) {
                return false;
            }

          • in the end of func we should check that cur trie is actually the end of word:

            return cur->IsEnd

      • startsWith
        • startsWith is almost the same as search, but
          • we don't need to check that last Trie is end of word, so in the end of the func we just return true

            return true

  • Add and Search Word
    • time - O(N∗26^M):
      • almost as previous one but:
        • during search if word[i] == '.', then just try to run search for word[i+1:] using cur->Children[...try all non-null...]
  • Word Search II
    • time - O(M∗(4∗3(L−1))), space - O(N):
      • Main idea:
        • create Trie tree for words
        • iterate through board and using DFS check if any word from words can be made up

• Heap

  • Merge K Sorted Lists
    • time - O(Nlogk), space - O(K)
      • create priority_queue (e.g. heapq in python)
      • add nodes to priority_queue
      • create result_node(val=0)
      • save start of result sequence: root = result_node
      • add smallest_node from priority_queue to result_node and add smallest_node.next to priority_queue
      • smallest_node = priority_queue.pop() # pop smallest element
      • priority_queue.put(smallest_node.next)
      • return root.next
  • Top K Frequent Elements
    • time - O(N), space - O(N)
      • calc frequency of each num

        unordered_map<int, int> count;
        count.reserve(nums.size());
        
        for (const auto& num : nums) {
            count[num]++;
        }

      • add to buckets where index = frequency, vals = list of nums with such frequency

      vector<vector<int>> bucket (nums.size() + 1);
      for (auto &p : count) {
          bucket[p.second].push_back(p.first);
      }

      • iterate through bucket in reverse to get most frequent nums first. return res as soon there are enough vals:

        for (int z = bucket.size() - 1; z >= 0; z --) {
      
          for (int j = bucket[z].size() - 1; j >= 0; j--) {
      
              if (res.size() == k) {
      
                  return res;
      
              }
      
      
              res.push_back(bucket[z][j]);
      
          }
      
      }

  • Find Median from Data Stream
    • time - O(log n), space - O(N)
      • to solve this problem we need to priority queues:
        • smaller, bigger.
        • smaller.top() is biggest val from smaller, bigger.top() is smallest val from bigger.
      • when we add new num, we add it according to these rules:
        • Biggest val of smaller should be always SMALLER than smallest val from bigger.
        • Difference between smaller.size() and bigger.size() should be <= 1. if difference becomes bigger than 1 -> we rebalance smaller and bigger queues, BUT DO NOT VIOLATE previous rule (biggest val of smaller should be always SMALLER than smallest val from bigger)
      • how do we find median?
        • if smaller.size() > bigger.size()
          • median = smaller.top()
        • if bigger.size() > smaller.size()
          • median = bigger.top()
        • else
          • median = (smaller + bigger) / 2.0

Notes

I think I should go back and solve this questions again:

• Array
  • 3Sum. Cheated for this question.
  • Maximum Product Subarray
• Binary
  • Sum of Two Integers. Cheated for this question.
• Dynamic Programming
  • Coin Change
  • Longest Increasing Subsequence
  • Longest Common Subsequence. Cheated.
  • Word Break. Cheaaated. However, i watched Bottom-Up solution, but implemented Top-down, so it's just half cheating
  • Combination Sum IV. I cheated.
• Graph
  • Course Schedule. Cheated, didn't even rewrite in C or Erlang.
  • Pacific Atlantic Water Flow. Even after watched explanation by NeetCode spent about 2 hours to implement. I surely need to come back to this.
  • Longest Consecutive Sequence
  • Alien Dictionary (Premium)
  • Graph Valid Tree (Premium)
• Interval
  • Non-overlapping Intervals
  • Reorder List
• Matrix
  • Set Matrix Zeroes
• String
  • Longest Repeating Character Replacement
• Tree
  • Binary Tree Maximum Path Sum
  • Construct Binary Tree from Preorder and Inorder Traversal
• Heap
  • Top K Frequent Elements
  • Find Median from Data Stream Also, I think I can find better approach for this problems:
• Missing Number
• String
  • Longest Repeating Character Replacement
  • Minimum Window Substring

Other algorithms

• Yandex
  • According to this article, these problems can be asked on interview:
    • Permutation in String
    • Max Consecutive Ones III
    • Find Duplicate Subtrees
  • Interview on YouTube
    • Squares of Sorted Array
• Designs. There are some cool deisgns, explore them, I think it will help on interviews.
  • LRU cache
  • Shuffle an Array
  • ... explore and find some other cool designs to implement

BFS

• solve several algorithms with BFS, not DFS

Divide and conquer

TODO: also need to solve some divide and conquer problems

Greedy

TODO: also need to solve some greedy problems

Yandex Contest

Solutions can be found in yandex_trainings directory

Explanations

• A_mushrooms
  • O(n):
    1. find vasya's and masha's sum
    2. find vasya's mushrom with smallest weight and masha's mushroom with biggest weight
    3. if masha's biggest mushroom is bigger than smallest vasya's mushroom, then give mushroom to vasya
• 1_B_mother
  • O(1)
    • to solve this task you need dfs or bfs
    • from current state you should try to any possible next_state (if next_state is not in path)
    • if both items are at home -> time = min(best_time, time)
    • state should consist of these elements:
      • curr_location ('d', 'p', 's')
      • items in hands
      • items at home
• 1_C_cybersecurity
  • O(n):
    • you can't replace "a" with char "a", so for each "a" (or any other letter) the number of combinations is the same.
    • number of combinations in "aabc" is (qty of a) * (qty of other letters), so for "a" it would be 2 * 2 (baac, abac, caba, acba). then do the same with "bc", then with "c"
    • and don't forget to add 1 to res, because we also should include original password
• 1_D_contest
  • take at least one problem from each theme
  • take any problems until the len(res) == k
• 1_E_increment
  • for some z: if n mod 10 = z, then after I iterations n mod 10 = z again. You need to find frequency of such repeations and interval between first and second occurances to calculate the rest.
• 1_F_plus_minus_question
  • Calculate biggest row sum and smallest col sum assuming that ? is + for rows and ? is - for cols. However, NOTICE that if grid[i][j] = ?, then 2 should be extracted from diff.
• 1_G_5_sequence
  • O(i*j):
    • for each (i,j) save:
      • vertical length (curRow[j].vert = prevRow[j].vert + 1),
      • left to right diagonal length (curRow[i].from_left_to_right = prevRow[i-1].from_left_to_right +1),
      • right to left diagonal length,
      • horizontal length (using curRow[i-1]).
      • If some length == 5, then print Yes and stop program. If length == 5 never happened -> print No
• 2_A_ball
  • O(i):
    • steps[0] = 0, steps[1] = 1, steps[2] = 2, steps[3] = 4, steps[i] = steps[i-3] + steps[i-2] + steps[i-1]
    • return steps[N]
• 2_B_river
  • 
  • O(n):
    • on each input[i] calc the best way to get to left side and to get to right side
    • e.g. if input[i] == 'l', then
      • best_l = min(prev_l + 1, prev_r+1)
      • best_r = min(prev_l+1, prev_r)
      • prev_l, prev_r = best_l, best_r
• 2_C_intervals
  • O(N * log(n))
• 2_D_dictionary
  • O(len(word) * len(word_dict)):
    • every time when word[i:].startswith(word_dict[j]), we do this dp[i + len(word_dict[j])].append(copy(dp[i][0]) + [j]).
    • e.g. we have input string "joja" and word_dict: "joj", "jo", "ja":
      • dp = [[], [], [], [], []]
      • i = 0 ("joja")
        • j = 0 ("joj")
          • "joja"[i:].startswith("joj"), so now dp becomes:
            • dp = [[], [], [], [0], []]
        • j = 1 ("jo")
          • "joja"[i:].startswith("jo"), so now dp becomes:
            • dp = [[], [], [1], [0], []]
        • j = 2 ("ja")
          • "joja"[i:].startswith("jo") is false, so we don't update dp
      • i = 1 ("oja")
        • there is no matching word from worddict for "joja"[i:]
      • i = 2 ("ja")
        • j = 2 ("ja")
          • "joja"[i:].startswith("jo"), so now dp becomes:
            • dp = [[], [], [1], [0], [1,2]]
            • STOP HERE, because we already found solution: [1,2] ("jo ja")
  • Note: this can be solved O(len(word) * log(word_dict)) if we use binary search to find matching words from word_dict
• 2_E_tower
  • O(N):
    • Solution can be divided in 2 steps:
      1. make array towers where tower[i] is safety of tower which last column is i
      2. make array dp where dp[i][0] = best solution of 0..i:
         • include = include = towers[i] + dp[i-K][0]
         • exclude = sorted((val, prev_vals) for val, prev_vals in dp[i-K+1:i+1])[-1]
         • then we compare exclude and include and make decision
• 2_F_game
  • O(N):
    • if cur_line[i] is reachable:
      • cur_line[i] = best_reachable_val_of_previous_raw + (1 if line[i] == 'C' else 0)
    • else
      • cur_line[i] = 0
    • IMPORTANT: stop if next row in unreachable:

      WW.
      .WW  # this one is unreachable
      

• 2_G_stairs
  • O(N^3):
    • dp[0][0] = 1
    • dp[total][first_row] = number of possible stairs, which consist of total cubes and which first row consists of first_row cubes
    • dp[total][first_row] = dp[total-first_row][first_row-1] + dp[total-first_row][first_row-2] + ... + dp[total-first_row][1]. In this way we calculate all possible ways to place cubes when total sum is total and there are first_row cubes in first row
    • But remember that first_row <= total
• 2_H_matchsticks
  • O(1):
    • if 1 matchstick is left, then person wins:
      • he wins (can remove 1 last stick)
    • if 2 matchsticks:
      • win (can remove 2 last sticks)
    • if 3 matchsticks:
      • win (can remove 3 last sticks)
    • if 4 matchsticks:
      • loss (no matter how many matchsticks you take - opponent will win)
    • if 5 or 6 or 7:
      • win (because can remove sticks and get 4 which means that opponent will lose)
    • if 8:
      • loss (because can't remove enough sticks to get to number where opponent will lose)
    • as we can see the if N % 4 == 0, then person loses
• 2_I_chain
• 2_J_masquerade
  • O(L * N * Fmax):
    • dp[s][k] = best(Cost(k ,t) + dp[s-t][k-1] for t in 0..F[k])
      • so we calculate best cost for s meters and kth house using previous results
    • however, sometimes t can be >= than s. In that case we do this: dp[s][k] = min(dp[s][k], Cost(k, t))
      • so if the best variant is to just buy more or equal to s meters in shop k, then buy it in shop k
• 3_A_shelf
• 3_B_from_dead_end_to_dead_end
  • i don't know complexity, but it's pretty fast:
    • gradually simultaniously explore all nodes starting from leaf nodes. Example:
      • Tree:
      • Mark that the fastest way to get to leaf nodes takes 0 steps:
      • Mark neighbor nodes with fastest way to get to them:
      • When exploring next neighbor of 2 we find that it is already explored. So, we found the result: 1-2 path + 2-3 path + best path to 3 = 1 + 1 + 1 = 3
• 3_C_advertisement
  • O(log(n) * n):
    • By binary search find matching k
    • I used brute force algorithm to check if k matches. Since I used C++, I didn't really care about optimization of this thing 🙂
• 3_D_currency_exchange
  • sort tables and save values like this [ [val1, orig_idx1], [val2, orig_idx2] ]. in this way it would be easier to determine original indexes for answer.
  • iterate with i through sorted tables
    • target = P / val_i
    • with binary search find best j for this target WHICH IS NOT EQUAL TO i
    • if val_i / val_j is smaller than best_ratio, then save original indexes of those values as best indexes
  • print best indexes
• 3_E_feudalism
• 3_F_ancestor
  • Iterate through nodes. Before entering node, save current time, after exploring node, also save time. Like this:

    • The tree:

    • Save time before entering. Start with root node:

    • Explore children nodes:

    • Save time after node is processed:

    • Do the same with the rest

  • After we explored all nodes we can easily determine if the node is parent or not. 2nd node is child of 1st, because 1-10 interval includes 2-3. However 3rd node is not parent of 2nd, because 2-3 interval is not inside 4-9 interval.
• 3_G_gravity
• 3_H_pickup
• 3_I_expression_tree
• 3_J_interviews
• 4_A_office_trips
  • Iterate through all seconds since 00:00 till 23:59
    • Process 2 stations:
      • If trip starts at current second:
        • If any bus on current station, then use it AND don't forget to save that at arrival time on opposite station there should be +1 bus
        • If no available bus on station, then total_buses += 1
      • If there are buses left at current second, then in next second at current station they should be available
• 4_B_car_tax
  • O(m * log(n)):
    • Iterate through cars (q vals):
      • with binary search find index of greatest b (power) that is less than q (car's power)
      • take t (tax) for this index and multiply it by q
      • print result of multiplication
• 4_C_candidates_queue
  • Use Fenwick tree
• 4_D_friendship_won
• 4_E_repair_patholes
• 4_F_train
• 4_G_series_planning
• 4_H_boss_bonus
• 4_I_banner
• 4_J_autosport

Notes

• 2_C intervals was hard, it would be good practice to solve it again

Sorting algorithms

Habr Article

More advanced sorting algorithms

Algorithms:

• Bubble Sort
• Insertion Sort List
• Selection Sort
• Heap Sort
• Quick Sort
• Merge Sort

Data Structures Implementations

Cool Article about data structures

Also, I think before implementing data structures it would be helpful to solve designs on leetcode

Data Structures:

• Linked list
• HashMap
• Queue

Cool sources

• visualgo (supercool visualizations)
• Micheal Sambol (short videos about data structures)
• Abdul Bari (videos about algorithms and data structures)
• Leetcode patterns
• algo.monster (some algo course)
• [ ]