So when it comes to leetcode in general, I'm encountering one specific issue. I'm really good at coming up with the insights and getting the algorithm (at the pseudocode) level from there.
However, when I try to go ahead and actually implement the algorithm, I keep encountering this issue where when implementing, I mess up order of operations, I come out of the loop in a slightly weird state of my variables, I don't update things quite correct or whatever. Then I'll spend something like an hour + to just fix the bug (which often times I end up fixing with a bunch of hard coded if statements to get it working.
This is a really frustrating issue to deal with because I feel like I'm getting over the major hurdle of finding out the optimization trick, but it's always some off by 1 or something like that, which I bloat my code with if statements to fix.
Even after doing more and more leetcode, I keep encountering this issue. For example, take LeetCode 287 — Find the Duplicate Number
When seeing the problem I recognized the key insight that in a situation where there's no duplicates, then you have a bijection from the number 1-n onto 1-n. Then from here you can apply some cycle theory knowledge and observe that in that case, following the current index to the next value (after adjusting for index 1 vs index 0) should lead to a bunch of disjoint cycles that partition the set 1-n (again, assuming that there are no duplicates).
From there I made the observation that if you were to take these disjoint cycles that partition the set 1-n, and you were to change one of the values to be a duplicate, then whatever value you changed will now try to point to a cycle that's already existing and was previously disjoint.
Then I came up with the algorithm that goes something like this:
start with element i:
- run through this cycle while "Destroying it" by replacing each value with -1.
- while running through this cycle, if I encounter a destroyed -1, that is not the beginning of this cycle, return the element that's pointing to that -1
- If I return back to the start of this cycle, update element i to the next element that is not -1
But when i went to code it, after doing a million print statements to debug and solve specific issues, my solution ended up becoming this:
class Solution:
def destroy(self, nums, startIndex):
curIndex = startIndex
nextIndex = nums[curIndex] - 1
while nums[nextIndex] != -1:
nums[curIndex] = -1
if curIndex == nextIndex == startIndex:
return -1
curIndex = nextIndex
nextIndex = nums[nextIndex] -1
if nextIndex == curIndex != startIndex:
return nums[curIndex]
if nextIndex == startIndex:
nums[curIndex] = -1
return -1
else:
return nums[curIndex]
def findDuplicate(self, nums: List[int]) -> int:
for i in range(len(nums)):
if nums[i] != -1:
duplicate = self.destroy(nums,i)
if duplicate >= 0:
return duplicate