NeetCode Solves Unprepared LeetCode Hards via Core Invariants

Testing Neetcode With 3 Leetcode Hards (Live Whiteboarding) — Ryan Peterman

Ryan Peterman

First-principles reasoning and structural invariants allow candidates to reconstruct optimal solutions to complex coding problems without relying on rote memorization.

AI-assisted summary of Testing Neetcode With 3 Leetcode Hards (Live Whiteboarding) — original source. Check the original for full context.

Source published:

Key ideas

  • Put on the spot with three random LeetCode Hard problems without preparation, NeetCode demonstrates how deriving solutions from first principles and core algorithmic patterns matters more than rote memorization—even on problems he has not touched in five years. (0:00)
  • For Edit Distance (LeetCode #72), framing the problem first as a three-way recursive decision tree (insert, delete, replace) directly yields an O(n × m) time and space 2D dynamic programming table where each cell represents prefix subproblems. (0:00)
  • In Median of Two Sorted Arrays (LeetCode #4), because the combined length of the two arrays is fixed, binary searching a partition cut in one array automatically determines the complementary partition boundary in the second array. (5:16)
  • Solving N-Queens II (LeetCode #52) relies on an exponential backtracking search optimized with four hash sets that provide O(1) conflict checks across rows, columns, anti-diagonals (row + col), and main diagonals (row - col). (12:05)

Detailed notes

## Background Published by Ryan Peterman on YouTube on October 5, 2026, this video features an unscripted whiteboarding challenge with popular programming educator NeetCode. The session is an excerpt from a longer interview where Peterman tests NeetCode's cold algorithmic problem-solving abilities by presenting him with three random LeetCode Hard questions.

## TL;DR In this whiteboarding demonstration, NeetCode works through three classic LeetCode Hard problems without advance preparation: Edit Distance (#72), Median of Two Sorted Arrays (#4), and N-Queens II (#52). For Edit Distance, he derives the recursive decision tree for string transformations and maps it into a 2D dynamic programming grid. On Median of Two Sorted Arrays, he relies on first principles to reason through binary search partitions across two sorted sets to achieve optimal complexity. Finally, for N-Queens II, he sketches out an efficient backtracking strategy, demonstrating how to track conflicting rows, columns, and diagonal lines in constant time using coordinate sums and differences.

## Atmosphere & style The session feels remarkably candid, relaxed, and authentic, playing out like an informal peer-to-peer technical interview between software engineers. NeetCode approaches each problem with self-deprecating humor and honesty, openly laughing when he forgets specific formulas or admits how tricky partition boundary edge cases can be. Peterman provides encouraging, grounded nudges that keep the pace moving naturally. Watching it feels reassuring and demystifying, illustrating that even top algorithm educators solve hard problems iteratively through fundamental reasoning and visual sketches rather than flawless rote memorization.

## Bulletin - [00:00](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=0s) Put on the spot with three random LeetCode Hard problems without preparation, NeetCode demonstrates how deriving solutions from first principles and core algorithmic patterns matters more than rote memorization—even on problems he has not touched in five years. - [00:00](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=0s) For Edit Distance (LeetCode #72), framing the problem first as a three-way recursive decision tree (insert, delete, replace) directly yields an O(n × m) time and space 2D dynamic programming table where each cell represents prefix subproblems. - [05:16](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=316s) In Median of Two Sorted Arrays (LeetCode #4), because the combined length of the two arrays is fixed, binary searching a partition cut in one array automatically determines the complementary partition boundary in the second array. - [12:05](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=725s) Solving N-Queens II (LeetCode #52) relies on an exponential backtracking search optimized with four hash sets that provide O(1) conflict checks across rows, columns, anti-diagonals (row + col), and main diagonals (row - col).

## Key takeaways - [00:00](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=0s) Because Edit Distance (LeetCode #72) allows character insertion, deletion, and replacement, any arbitrary string can always be transformed into another regardless of initial length differences. - [00:00](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=0s) When comparing characters in Edit Distance, matching characters advance both pointers at zero cost, whereas mismatched characters require branching across all three edit operations because a greedy choice cannot predict future alignments. - [00:00](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=0s) Caching overlapping subproblems in the Edit Distance decision tree leads to an O(n × m) time and space 2D dynamic programming grid where each cell computes the minimum cost of adjacent insert, delete, and replace transitions plus one. - [00:00](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=0s) In live interviews, transitioning to code early when building 2D dynamic programming solutions helps clarify index transitions and boundary edge cases better than trying to hold the entire grid state mentally. - [05:16](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=316s) When tackling Median of Two Sorted Arrays (LeetCode #4) from first principles, drafting a concrete numerical example helps navigate common pitfalls like overlapping intervals, unequal array lengths, and duplicate values. - [05:16](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=316s) Finding the median of two sorted arrays differs based on parity: an odd combined size targets a single middle element, while an even combined size requires averaging two middle numbers and handling extra off-by-one boundary cases. - [05:16](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=316s) Because the total number of elements is fixed in Median of Two Sorted Arrays, performing binary search on a partition boundary in one array automatically dictates where the partition cut must land in the second array. - [05:16](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=316s) Working from first principles and visual intuition allows a candidate to recover complex binary search partitioning logic even five years after last studying the problem. - [10:05](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=605s) Sketching out an n × n visual grid is essential in N-Queens II (LeetCode #52) to spot spatial patterns and design efficient bookkeeping for queen attack paths. - [11:04](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=664s) While tracking occupied rows and columns in N-Queens II only requires simple hash sets of indices, tracking diagonals efficiently requires a coordinate invariant trick. - [12:05](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=725s) Along any anti-diagonal, incrementing the row while decrementing the column keeps the sum (row + col) constant; along any main diagonal, incrementing both coordinates simultaneously keeps the difference (row - col) constant. - [14:41](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=881s) Maintaining four hash sets (rows, columns, positive diagonals, and negative diagonals) enables O(1) validity checks at each square to prune invalid branches immediately within an exponential backtracking search space.

## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=0s) Tackling Edit Distance (LeetCode #72)

Ryan opens the session by throwing a classic LeetCode Hard problem at NeetCode: Edit Distance. Given two strings, `word1` and `word2`, the objective is to return the minimum number of operations required to transform `word1` into `word2`. The permissible operations are inserting a character, deleting a character, or replacing a character. NeetCode immediately recognizes the problem type, noting that while he does not recall all the fine-grained implementation details off the top of his head, he knows the core algorithmic pattern: formulating a recursive decision tree and caching overlapping subproblems to yield a dynamic programming (DP) solution. Because insertion, deletion, and replacement are allowed, any arbitrary string can unconditionally be transformed into another, regardless of differences in initial string lengths.

NeetCode begins tracing out the decision tree using pointers across the two words. When the characters at the current pointers match, no edit cost is incurred, and the pointers simply advance forward. However, when the characters differ, the algorithm cannot "predict the future" greedily, requiring a brute-force branching across all three edit options: 1. Deleting a character from `word1` 2. Inserting a character into `word1` 3. Replacing (modifying) the character in `word1` to match `word2`

```mermaid flowchart TD accTitle: Edit Distance Decision Tree accDescr: Branching logic when comparing characters in word1 and word2 during edit distance calculation.

Start["Compare word1[i] and word2[j]"] --> Match{"Do characters match?"} Match -->|"Yes: word1[i] == word2[j]"| Advance["Advance both pointers (i+1, j+1)<br/>Cost = 0"] Match -->|"No: word1[i]!= word2[j]"| Branch["Branch 3 Operations<br/>Cost = 1 + min(...)"]

Branch --> OpInsert["Insert character<br/>(i, j+1)"] Branch --> OpDelete["Delete character<br/>(i+1, j)"] Branch --> OpReplace["Replace character<br/>(i+1, j+1)"] ```

From this recursive formulation, NeetCode outlines the transition into a 2D bottom-up dynamic programming table of size $O(n \times m)$ time and space complexity, where $n$ and $m$ are the lengths of the respective strings. When Ryan asks what an individual cell in that grid represents, NeetCode laughs, acknowledging that indexing DP tables is often where people get tripped up. He explains that each cell corresponds to the subproblem answer for the prefixes (or substrings) up to indices $i$ and $j$. To compute the value of any given cell, the algorithm looks back at adjacent neighboring cells representing the insert, delete, and replace transitions, taking the minimum cost among them plus one. NeetCode notes that in a real interview setting, he typically starts writing code at this stage because working directly with indices in code helps clarify edge cases and directional transitions better than trying to hold the entire grid state in his head. Ryan confirms NeetCode is on the right track, acknowledging that completing it is simply a matter of careful case analysis.

[05:16](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=316s) Median of Two Sorted Arrays (LeetCode #4)

Ryan shifts to a notoriously tricky binary search problem: finding the median of two sorted arrays. NeetCode admits that this problem is "always annoying" and begins drafting a concrete numerical example with nine total elements across two arrays to derive the intuition from first principles. He points out common interview pitfalls, such as overlapping intervals, unequal lengths, and duplicate values between the arrays. NeetCode reflects on interview time management: while he could take the time to align all elements sequentially and even color-code them to visualize the partitions, he knows the optimal target complexity requires some flavor of binary search, so his primary focus is deducing the partitioning trick.

He attempts to eliminate sections of the arrays using two pointers (`left` and `right`) in both arrays simultaneously, laughing when he admits, "I don't remember how to do that." Ryan briefly mentions a target before immediately clarifying that the problem strictly seeks the median, which NeetCode notes actually constrains the search space favorably: - For an odd combined size (e.g., $9$ elements), the goal is to pinpoint the exact $5^{\text{th}}$ element overall. - For an even combined size, the median requires averaging the two middle numbers, introducing additional off-by-one boundary cases.

NeetCode reasons that because the total length is fixed, one does not need to perform an independent binary search across both arrays; instead, performing binary search on a partition boundary in one array automatically dictates where the corresponding partition cut must land in the second array. By comparing the medians or boundary elements of both partitions, one can determine whether the combined partition is shifted too far to the left or too far to the right. NeetCode jokes that wrestling with these partition boundary edge cases is the moment in an interview where he would need to grab a cup of coffee. He remarks that it has been five years since he originally made his YouTube explanation video for the problem and had not touched it since, but emphasizes that working from first principles allows a candidate to get remarkably close to the right intuition even without rote memorization.

[10:05](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=605s) Introducing N-Queens II (LeetCode #52)

Ryan raises the stakes with another Hard problem: N-Queens II. Given an $n \times n$ chessboard, the task is to return the total number of distinct board configurations where $n$ queens can be placed such that no two queens attack each other. Ryan recaps the standard chess rules for queens: they can attack any piece sharing the same row, column, or diagonal. NeetCode immediately starts sketching out an $n \times n$ grid, observing that visual layout is essential for spotting the underlying spatial patterns and bookkeeping tricks needed to track conflicting columns and diagonals efficiently.

[11:04](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=664s) Formulating the Backtracking Strategy and the Diagonal Challenge

NeetCode begins breaking down LeetCode #52 (N-Queens II) from memory, asking himself how to systematically prevent queens from attacking one another. He identifies that a trial-and-error backtracking algorithm is the best and most standard approach. Checking for shared rows and columns is straightforward: one can simply maintain hash sets for rows and columns to track occupied lines.

The crux of the problem lies in efficiently tracking the diagonals. Unlike rows and columns, there is no direct coordinate label for a diagonal line on a grid. Addressing the common viewer question of "how would you know this?", NeetCode candidly admits that it relies on a specific mathematical trick that he certainly did not invent himself, but remembers as the standard way to model diagonals cleanly.

```mermaid flowchart TD accTitle: N-Queens Board Conflict Tracking accDescr: Tracking queen attacks across rows, columns, positive diagonals, and negative diagonals using coordinate formulas. subgraph Constraints["Coordinate Invariants for Attacks"] R["Row: r"] C["Column: c"] D1["Anti-Diagonal: r + c"] D2["Main Diagonal: r - c"] end subgraph StateSets["Hash Sets for O(1) Lookup"] SR["rows = set()"] SC["cols = set()"] SD1["pos_diag = set()"] SD2["neg_diag = set()"] end R --> SR C --> SC D1 --> SD1 D2 --> SD2 ```

[12:05](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=725s) Deriving the Diagonal Invariants: Sums and Differences

To explain the diagonal invariant, NeetCode visualizes placing a queen on a square such as row 1, column 1. Moving along one diagonal direction increments the row index by 1 while decrementing the column index by 1 (or vice versa). Because one coordinate increases by the exact amount the other decreases, their sum remains perfectly constant along that entire anti-diagonal line (e.g., $1 + 1 = 2$). Thus, `row + col` serves as a unique identifier for that diagonal.

When it comes to the opposing diagonal, NeetCode pauses for a moment, admitting with a small laugh that he does not instantly remember the exact formula off the top of his head. Ryan Peterman clarifies the objective: NeetCode is simply trying to achieve rapid $O(1)$ diagonal membership checks to determine whether a given diagonal is already under attack. NeetCode walks through the coordinates along that line—$(0, 0)$, $(1, 1)$, $(2, 2)$—and notices that both indices grow simultaneously. He concludes that taking the difference rather than the sum keeps the value constant: - For anti-diagonals (slanted one way), the sum `row + col` remains identical. - For main diagonals (slanted the other way), the difference `row - col` remains identical.

[14:41](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=881s) Decision Tree, Backtracking Execution, and Time Complexity

With four hash data structures established (rows, columns, positive diagonals, and negative diagonals), the backtracking procedure iterates through board positions. At each candidate square, the algorithm checks whether placing a queen violates any of the four hash sets. If the square is free from attacks, the queen is placed, the sets are updated, and the search recurses deeper; otherwise, the square is skipped, pruning invalid paths immediately. Ryan Peterman summarizes the approach as a brute-force search augmented with constant-time validity checks before each step forward.

When discussing the runtime complexity, NeetCode notes that while each hash set lookup is $O(1)$, the overall recursion tree grows substantially. While he does not give an exact closed-form bound off the top of his head—mentioning it could be roughly exponential or on the order of $N^N$—it represents the optimal backtracking solution for the problem. Ryan agrees that the design is completely sound, wrapping up the challenge.

- **Data structures used**: Four hash sets to track occupied rows, columns, anti-diagonals (`r + c`), and main diagonals (`r - c`). - **Pruning mechanism**: Skip squares where coordinates already exist in any of the four sets. - **Complexity intuition**: $O(1)$ membership checks per placement decision, operating over an exponential backtracking search space.

## Notable quotes > [05:16](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=316s) I don't remember how to do that. — NeetCode

> [11:04](https://www.youtube.com/watch?v=rbtO3a6Qb00&t=664s) how would you know this? — NeetCode

## Mentioned Ryan Peterman, NeetCode, YouTube, LeetCode, LeetCode #72: Edit Distance, LeetCode #4: Median of Two Sorted Arrays, LeetCode #52: N-Queens II

## Video description During the full interview we did here: https://youtu.be/K15dND_Kfvg

I was curious how good he was at Leetcode without any preparation. Here's a little rough cut of me asking him three random Leetcode hard questions and seeing what he came up with

0:00 — LeetCode #72: Edit Distance https://leetcode.com/problems/edit-distance/

5:16 — LeetCode #4: Median of Two Sorted Arrays https://leetcode.com/problems/median-of-two-sorted-arrays/

10:05 — LeetCode #52: N-Queens II https://leetcode.com/problems/n-queens-ii/

[Source](https://www.youtube.com/watch?v=rbtO3a6Qb00)

中文简报

NeetCode依托核心不变量即兴拆解LeetCode Hard题 通过第一性原理推导与结构不变量，求职者无需死记硬背即可重构复杂编程题的最优解。 在本次白板演示中，NeetCode在未提前准备的情况下现场推导了三道经典LeetCode Hard难题：编辑距离（#72）、寻找两个正序数组的中位数（#4）以及N皇后 II（#52）。对于编辑距离，他梳理出字符串转换的递归决策树，并将其转化为二维动态规划网格。在寻找两个正序数组的中位数一题中，他基于第一性原理推导跨两个有序集合的二分搜索划分，从而达到最优复杂度。最后，针对N皇后 II，他勾勒出高效的回溯策略，展示了如何利用坐标和与差以常数时间追踪产生冲突的行、列及对角线。 在毫无准备的情况下被随机抽取三道LeetCode Hard题，NeetCode展示了即使面对五年未接触的题目，依靠第一性原理与核心算法模式推导解法也远比死记硬背更为关键。 (0:00) 对于编辑距离（LeetCode #72），首先将问题建模为三叉递归决策树（插入、删除、替换），即可直接推导出时间与空间复杂度均为O(n × m)的二维动态规划表，其中每个单元格均对应前缀子问题。 (0:00) 在寻找两个正序数组的中位数（LeetCode #4）中，由于两数组合并后的总长度是固定的，因此在一个数组中二分搜索划分切片会自动确定第二个数组中的互补划分边界。 (5:16) 求解N皇后 II（LeetCode #52）依赖于指数级回溯搜索，并通过四个哈希集合进行优化，实现了对行、列、反对角线（行+列）及主对角线（行-列）的O(1)冲突检查。 (12:05)

Reading summary

In a live whiteboarding session hosted by Ryan Peterman, NeetCode demonstrates how challenging algorithmic problems can be resolved through structural problem patterns—such as dynamic programming transitions, binary search partitioning, and mathematical coordinate invariants—even when fine-grained implementation details are not memorized in advance. Dynamic Programming Transitions for Edit Distance (0:00) When solving LeetCode #72 (Edit Distance), NeetCode frames the task of transforming `word1` into `word2` using insertions, deletions, or replacements as a recursive decision tree. Because greedy choices cannot forecast optimal alignments, mismatched characters require branching across all three permissible edits at a cost of one plus the minimum of the branches, whereas matching characters simply advance both string pointers at zero additional cost. Managing Grid Indexing and DP State Complexity (0:00) This recursive tree maps directly to a 2D bottom-up dynamic programming table of size $O(n \times m)$, where $n$ and $m$ represent string lengths. Each cell stores the optimal result for string prefixes up to indices $i$ and $j$, computed from the values of adjacent neighboring cells representing the three operations. NeetCode points out that indexing such tables often causes confusion in interviews; consequently, he prefers writing code early in the process, as directly manipulating indices helps clarify edge cases and directional transitions better than tracking the entire grid mentally. Single-Array Binary Search for Median Determination (5:16) Addressing LeetCode #4 (Median of Two Sorted Arrays), NeetCode rejects simultaneous two-pointer array traversals in favor of a binary search partitioning strategy. Because the combined length of the two sorted arrays is fixed, establishing a partition cut in one array automatically determines the corresponding cut location in the second. Comparing boundary values around the split reveals whether the partition needs to shift left or right. Navigating Partition Boundaries and Edge Cases (5:16) NeetCode highlights that fixed lengths narrow the search: an odd total size targets a single median index, while an even total size requires averaging two boundary values and introduces off-by-one boundary risks. Although he admits to not having reviewed the exact partitioning details in five years, NeetCode emphasizes that constructing concrete numerical examples allows an interviewee to reconstruct the necessary binary search logic from first principles without relying on rote memorization. Coordinate Invariants and Pruning in N-Queens (11:04) For LeetCode #52 (N-Queens II), the objective is to count valid placements of $n$ queens on an $n \times n$ board such that no two pieces share a row, column, or diagonal. NeetCode structures the solution around backtracking, noting that while row and column conflicts can be recorded with standard index sets, diagonals require mathematical invariants. Specifically, anti-diagonals share a constant coordinate sum (`row + col`), while main diagonals share a constant difference (`row - col`). Pruning Search Paths in Backtracking Trees (14:41) By maintaining four hash sets for occupied rows, columns, positive diagonals, and negative diagonals, the algorithm performs $O(1)$ validity checks at each candidate square before placing a queen and recursing. Peterman characterizes this as a brute-force search augmented by constant-time validation that prunes invalid paths immediately. While the overall recursion tree remains roughly exponential, NeetCode explains that this pruning yields the standard optimal backtracking solution for the problem. The session illustrates that solving complex interview problems relies on identifying core mathematical invariants and state-transition models rather than recalling memorized code. While index boundaries and partition mechanics remain prone to manual slips during live interviews, grounding the approach in decision trees and constant-time tracking sets ensures a structured path toward the optimal solution.

Source quotes

[5:16] NeetCode: I don't remember how to do that. [11:04] NeetCode: how would you know this?

Original transcript

[0:00] In this problem, given two strings, I [0:03] let's call it word one and word two. I [0:06] want you to return the minimum number of [0:09] operations required to convert word one [0:12] into word two. And the operations you [0:15] can perform are either inserting a [0:18] character, deleting a character, or [0:20] replacing a character. How would you do [0:22] this problem? Okay. So, I guess I'm just [0:26] thinking in terms of like an example [0:28] right now, but I do know like what this [0:30] question is and I know like the patterns [0:32] it falls into. Um, but I don't know like [0:36] all the details. But, um, I do know off [0:39] the top of my head that this problem can [0:40] be solved with recursion and then that [0:42] can like lend itself into the DP [0:44] solution. So basically as I would go [0:48] through this um I guess it's not [0:49] necessarily true that they're going to [0:51] be the same length and they don't have [0:52] to be since we're we can insert, delete [0:54] or modify. So it's 100% true that we can [0:58] convert one to the other. It's just a [0:59] matter of like the operations which I [1:00] think you mentioned as part of the [1:02] question. Um, so I guess uh there's [1:06] three uh possibilities or maybe there's [1:10] only two, but one is that they're equal. [1:12] Um, in which case you just shift the [1:15] pointer. So you can kind of just ignore [1:17] that. And then same thing here. Now here [1:20] where uh they're different, this is [1:23] where it gets interesting because unless [1:25] we can like predict the future, we don't [1:26] really know which one would result in [1:28] the minimum. So in terms of like the [1:30] decision tree, it's just going to be a [1:32] matter of like brute forcing. So [1:36] um one would be to like delete the [1:40] character, one would be to insert, and [1:44] the other I guess would be to just [1:45] modify. And in this case, we're trying [1:47] to turn this word into that one. So we [1:50] would modify this one. And [1:54] that's going to be edit. [1:57] And then so among these [1:59] I guess the recursive way would be to [2:01] just uh solve this recursively and then [2:04] add like a cache which is dynamic [2:06] programming. Um but what I would do if I [2:10] was going to skip that recursive [2:11] solution what I would do is just kind of [2:12] roughly look at this try to figure out [2:14] what like the equation would be. And [2:16] when I say equation I mean like result [2:19] is going to equal like some uh DP call [2:22] maybe like the maximum of these three. [2:25] And then so uh if I was going to do the [2:29] actual DP solution which I think would [2:31] end up being like n * m time complexity [2:35] based on like the dimensions of this [2:36] grid uh you can kind of imagine like you [2:40] could take these two words and like [2:44] make like a grid out of them and then [2:46] you just like fill in that grid and it [2:48] would tell you the solution. [2:49] >> But what's the what's a cell in that [2:52] grid represent? [2:53] >> Yeah. So that's the hard part [laughter] [2:55] and it depends on how you set it up. I [2:57] always set it up a way that like most [2:59] people don't like, but I guess so if [3:02] this is the zero end, it would basically [3:05] be like, okay, what's the edit distance [3:07] of like the first character of each word [3:10] that's over here? Over here, it would be [3:11] a bit more interesting where it's like, [3:13] okay, this portion of the word and this [3:15] portion of the word. And so as you keep [3:17] filling these in, what you notice is [3:19] that like to if we're doing these three [3:22] calls, uh to fill in the last cell, it [3:25] would just be a matter of like looking [3:28] um in whatever direction. So uh like if [3:34] we were deleting a character from word [3:36] one, then we'd probably just look that [3:38] way. Uh yeah, or maybe I'm that [3:42] opposite. But anyways, this is where it [3:45] gets hard and this is where you actually [3:46] have to start thinking and they usually [3:48] I'll start writing the code at this [3:50] point. Um because that actually does [3:53] help me, but for some people maybe [3:55] they'll figure it out in their head [3:56] first. But if you go from the recursive [3:58] solution to DP, it's a lot easier. I [4:01] see. Okay. So the cell is the answer for [4:05] the substring up until that uh N and M. [4:09] And you you're saying you would give a [4:13] formula for how to build up the next [4:16] solution out of the existing ones that [4:19] you've done so far. [4:20] >> Yeah, that's right. And that kind of [4:21] like I'd probably spend more time on [4:23] this part just to make sure that I [4:25] really like understand what's going on [4:26] in terms of like the exact sub problem [4:30] because we're allowed to delete, insert, [4:32] or edit. [4:34] So I assume that they're all valid. I [4:36] assume like one of them like they they'd [4:38] all be necessary at some point unless [4:40] I'm like missing something off the top [4:42] of my head right now. Maybe like there's [4:43] a case where you'd never delete or you'd [4:45] never insert. Um but [4:49] like in this problem just going through [4:51] the example I can see that we just edit [4:52] twice. We'd edit here and then edit [4:54] here. We wouldn't do any delete or [4:56] insert. But maybe if I change the [4:57] example, um, [5:00] if I do this, [5:04] uh, well, maybe I should have done the [5:06] other way. But the idea is that like we [5:08] delete one character from from one [5:10] substring to get the other one. [5:12] >> I see. Okay. Yeah. I mean, I think I I [5:15] get what you're saying. You're clearly [5:17] going in the the right direction here. [5:19] We just would have to spend a bunch of [5:20] time figuring out the case analysis. [5:23] Um, okay. Let's let's try uh okay how [5:28] about this one? I know this is a a very [5:31] famous difficult problem which is um [5:35] let's say I give you uh two sorted [5:39] arrays and I want you to find the median [5:43] number among the two sorted arrays. How [5:47] would you how would you do that one? [5:49] >> Okay, this one's always annoying. Um, so [5:52] I'm going to like just try to craft an [5:54] example that hopefully [5:56] I can try to like derive the solution. [5:59] Even though I kind of know it off the [6:01] top of my head, I think you can reason [6:03] about the general idea. [6:07] Wonder if I can get a better. [6:09] Okay, so I picked these two arrays. I [6:12] might need to change the example because [6:14] the example is going to tell us like [6:15] what the solution is because I know [6:17] there's going to be edge cases. [6:20] For example, what if there's duplicates [6:22] like between the two arrays? What if [6:24] like one is further than the other? So, [6:25] I might like modify this, but uh we have [6:28] a couple duplicates and we have like [6:30] this one is going to be there. So, we [6:33] have like an array that's like kind of [6:35] overlapping. [6:37] Um I guess just for like [6:40] so this the fact that I don't know how [6:42] to solve this problem now. I'm already [6:43] thinking like okay, how do I manage my [6:45] time in a real interview? Because what I [6:47] want to do is like create a line with [6:50] all these elements. And maybe if I have [6:51] extra time, I'd even like color code to [6:54] help me think. But I know that the [6:57] solution is going to be some form of [6:58] binary search. And so I want to know [7:02] like if I can figure out the trick [7:06] because if I can do that, then I'll have [7:07] a chance of solving it. And if I can't [7:09] then I probably won't. I know it's going [7:12] to be a matter of like setting up the [7:14] pointers initially, left and right here, [7:17] and then left and right here, because [7:19] what we want to do right now [7:22] is eliminate part of the array. [7:26] But I don't remember how to do that. [7:28] [laughter] [7:28] So, okay, if I just had one array, what [7:31] I would do, and you gave me a target, [7:33] right? [7:34] >> Yeah. [7:35] >> So, [7:37] I want to know [7:38] >> Oh, wait. No, just find the median. [7:40] >> Oh, yeah. Median. media yet. Okay, [7:42] actually that I think that actually [7:44] makes it easier because maybe it [7:45] wouldn't be possible otherwise. [7:48] Okay, so median. So what that means is [7:51] we'd want like literally the middle [7:53] number. Okay, so the clue now that I [7:56] have is that like uh we have nine [7:59] elements total at least in this example. [8:02] So how can I like eliminate something? [8:05] Can I like do I know for sure that like [8:09] at least these three are not the median? [8:13] Not really. Because if we have nine [8:16] elements, I know the fifth one is the [8:18] median and these like technically we [8:22] could have like some elements here and [8:24] then maybe that could be the median. So [8:25] that's not going to work. So now I I [8:27] know for sure that to solve this problem [8:30] at each step we're going to have to look [8:32] at both arrays. But I still don't know [8:35] how to do. [laughter] [8:37] And so um I'll probably go through an [8:41] example. So now I'm thinking like can I [8:42] just go through this example like [8:44] without even trying to worry about the [8:45] solution just like somehow like on pen [8:47] and paper just like solve this problem [8:49] by like eliminating like portions of the [8:52] array at a time. I don't need to [8:54] eliminate from both arrays. I'd really [8:56] only need to do it from one array. Okay. [8:59] So how can I do it? So knowing that this [9:01] is the entire thing somehow can I like [9:04] look at three or like look at the median [9:06] in one of these to figure that out. I [9:08] think probably that's it. I think [9:10] probably I'd have to look at the median [9:11] here and the median here do some kind of [9:15] comparison [9:16] to figure out what I was talking about [9:18] earlier where like if we have like [9:21] nine elements the fifth one is like the [9:24] median that we're trying to find. And so [9:26] really all we want to know is like are [9:28] we here or are we here? So, I'm getting [9:30] closer, [laughter] but um [9:35] yeah, I know there's going to be some [9:36] off like some off by ones here because [9:39] like if there's just two elements, the [9:41] median is different where if it's just [9:43] like one element in the middle. So, [9:46] this is where I'd get like a coffee, [9:48] [laughter] [9:50] but I'm definitely close. Like I I do [9:52] not even remember this problem. I think [9:53] it's been like 5 years since I made the [9:55] video for it. I don't think I ever [9:57] solved it again. But you can see that [9:59] like from first principles you can [10:01] actually like get like a little bit [10:03] closer. [laughter] [10:06] Okay, let's let's make things a little [10:08] bit harder. So this question um given a [10:13] n byn chessboard I want you to figure [10:18] out the uh number of orientations [10:23] where you could place n queens such that [10:27] none of the queens are attacking each [10:29] other. So you know queens they attack in [10:32] all c cardinal directions and the [10:35] diagonals. [10:36] uh you need to find a number of distinct [10:40] solutions where you could place n queens [10:42] on this this board and none of them are [10:46] um hitting one another. [10:49] Okay, so [10:52] I'm just setting up the grid because [10:53] that's going to be like the most [10:55] important part to like visualize this [10:56] and I know that there's going to be [11:00] a trick involved. So [11:04] um okay so off the top of my head how do [11:06] we like break down this problem? One is [11:08] like we need to know are any queens [11:10] attacking each other in terms of like [11:13] the brute force solution the best way to [11:15] do that would be some kind of just like [11:17] trial and error like backtracking [11:18] approach. I think that's the best way to [11:20] do this uh problem from memory. Um, and [11:25] then what what's straightforward is that [11:28] if a queen is in the same like vertical [11:31] or horizontal [11:34] as another queen, it's pretty [11:35] straightforward because we can literally [11:38] just use some kind of like hash data [11:40] structure just to keep track of like the [11:43] row or like the column if it's going [11:47] that way. Um, but the hard thing is the [11:49] diagonals obviously because that's [11:52] changing. Like there's no like diagonal [11:54] here that tells you you're on like that [11:56] diagonal. But there's a trick. And so [11:59] people always ask, how would you know [12:00] this? Um, that's a good question. I [12:03] definitely didn't come up with it, but [12:05] the trick is this that okay because so [12:08] let's say I'm I'm on this square. Uh, [12:11] this is row one and column one. And if [12:16] I'm going along this diagonal, [12:19] uh, okay, I drew that wrong. But if I'm [12:21] going along that diagonal, [12:24] uh, if I go this way, I just increased [12:28] the row by one and I decreased the [12:31] column by one. If I go that way, I just [12:35] increased the column by one, but I like [12:39] decrease the row by one. So the trick is [12:43] that if I can like redraw this I guess [12:48] uh this diagonal one + one is going to [12:54] be two here. So like the sum of those [12:56] values can be used to define the [12:57] diagonal is basically uh the trick. So I [13:01] would solve this problem [13:03] pretty easily I guess just by having uh [13:07] four hash data structures and the key [13:10] for those uh data structures well two of [13:13] them are just going to be like a row or [13:14] and column set the other one is going to [13:16] be different it's going to be uh this [13:18] diagonal but also the other diagonal as [13:20] well which will have I think the [13:22] opposite [13:24] uh like okay as we go this way [13:29] it's just getting bigger. Um, [13:33] okay. I actually don't remember that. [13:35] But, um, [13:38] okay. So, now I'm thinking about it. Let [13:40] me just take like one second. [laughter] [13:49] Um, [13:53] >> so you're just trying to get quick [13:55] diagonal membership like given, you [13:58] know, is that is that occupied or not? [14:00] >> Yeah, exactly. It's just like a key [14:01] value lookup. [14:02] >> Yeah. [14:02] >> So, [14:04] um, [14:06] but as you're going this way, the [14:07] diagonal is different. It's like 0 + 0, [14:11] 1 + 1, 2 + 2. [14:15] So, okay. So I guess based on that uh I [14:19] would say that if we want it to be [14:21] constant the obvious thing that we can [14:23] do instead of adding both of these is [14:25] just taking the difference because uh we [14:28] on this diagonal we chose to add them [14:30] because then they would it would stay [14:32] the same value along that and on this [14:33] one we decide to take the difference [14:36] because if we just add them it's not [14:37] going to be the same. Um yeah so so the [14:41] approach would work. It was just that [14:42] that little trick. Um, but then other [14:46] than that, it's just like a hashbased [14:48] like lookup where we would um the [14:50] backtracking would basically be for [14:52] every single spot we either make a [14:54] decision of like whether we put a queen [14:56] there or we skip it. And um sometimes [15:00] we'd want to skip it if we already know [15:02] that there's like another queen [15:03] attacking that one. [15:04] >> Yeah. [15:05] >> But yeah, [15:06] >> I see. Okay. So you it's just brute [15:09] force with a bunch of checks to make [15:11] sure Okay. It's a valid step forward. [15:14] >> Yeah. So, I think I don't know off the [15:16] top of my head the complexity, but I'm [15:18] pretty sure it'd be optimal because at [15:20] each step, like each hash lookup would [15:22] be constant, but in terms of like the [15:24] complexity of this entire tree, [15:27] um, [15:29] it'd be pretty big. I don't know exactly [15:32] like it might be n to the power of n, [15:34] but it's definitely more than like [15:36] it's definitely exponential or [15:38] something. [15:39] >> Yeah. Yeah, I see. Yeah, I think that [15:41] would work. [laughter] [15:43] Shot ad.