Real example: Leetcode 665

Knowing interview principles is one thing. Applying them under pressure is another. To show you how the Five Keys transform a good candidate into a great one, let's walk through a real-world interview problem together:LeetCode 665: Non-decreasing Array.

The Problem: Given an array of integers nums, your task is to check if it could become non-decreasing by modifying at most one element. An array is non-decreasing if for all i where 0 <= i <= n-2, nums[i] <= nums[i+1].

Now, let's solve this, not like we're just trying to get a green checkmark on LeetCode, but like we're in a real interview at a top tech company.

Step 1: Master the Art of Clarification (Don't Assume!)

Before writing a single line of code, I need to understand the boundaries of the problem. This shows I am careful and consider the details before acting.

"Thanks for the problem. I have a few clarifying questions to make sure I fully understand the scope:

• What are the constraints on the size of the array? Can it be very large? (The description says up to 10,000, so an O(n^2) solution might be too slow. We should aim for something better.)
• What about the values in the array? Are they positive, negative, or both? (The constraints mention they can be from -100,000 to 100,000. This is good to know.)
• What should happen if the array is empty or has only one element? (An array with 0 or 1 elements is technically non-decreasing, so it should return true. This is a great edge case to confirm.)
• Just to confirm, "at most one" modification means I can make zero or one change, right? (Yes, that's correct.)"

By asking these questions, I've already demonstrated a professional mindset and identified key edge cases to test later.

Step 2: Think Aloud (Narrate Your Thought Process)

Now I'll outline my plan to the interviewer before I get lost in the code.

"Okay, so my goal is to find out if the array can be sorted with at most one change. This means the array can have at most one "dip" or "inversion," where nums[i] > nums[i+1].

I can iterate through the array with a single pass, keeping track of how many modifications I've made. I'll need a variable, let's call it modifications, initialized to zero.

When I find a dip at index i (where nums[i] > nums[i+1]), I've found a problem. I must use my one allowed modification right here to fix it. So, I'll increment my modifications counter. If I ever find a second dip, I know it's impossible, so I can immediately return false.

The tricky part is how to make the modification. When I find that nums[i] > nums[i+1], I have two choices:

1. Lower nums[i]: Make nums[i] = nums[i+1].
2. Raise nums[i+1]: Make nums[i+1] = nums[i].

Which one is better? Let's think about the element before the dip, at nums[i-1].

• If I lower nums[i], I need to make sure the new nums[i] is still greater than or equal to nums[i-1]. This is the safer option because it's less likely to cause a problem with future elements. For example, in [3, 4, 2], if I find the dip at 4 > 2, I should change the 4 to a 2 (making it [3, 2, 2]). But wait, that doesn't work because 3 > 2. So I must check nums[i-1].
• Let's refine this. When I find the dip nums[i] > nums[i+1]:
  • I look at nums[i-1]. If nums[i+1] is greater than or equal to nums[i-1] (e.g., in [3, 5, 4]), then it's safe to lower nums[i] to nums[i+1]. The array becomes [3, 4, 4], which is fine.
  • However, if nums[i+1] is less than nums[i-1] (e.g., in [4, 5, 2]), my only choice is to raise nums[i+1] to be equal to nums[i]. The array becomes [4, 5, 5].

This logic seems sound. I'll perform this check at each dip. If my modifications count ever exceeds 1, I'll return false. If I finish the loop, it means it's possible, so I'll return true."

Step 3: Write for Humans (Clean, Readable Code)

Now, I'll translate my thoughts into code, using clear variable names and structure.

Python

from typing import List

class Solution:
  def checkPossibility(self, nums: List[int]) -> bool:
    """
    Checks if an array can become non-decreasing by modifying at most one element.
    """
    modifications = 0
    
    for i in range(1, len(nums)):
      # Found a "dip" where the order is broken.
      if nums[i] < nums[i-1]:
        modifications += 1
        
        # If we need more than one modification, it's impossible.
        if modifications > 1:
          return False
          
        # This is the key decision: which element to modify.
        # If the element at i-2 is not a concern (either because it doesn't
        # exist or it's small enough), we can safely lower the previous element (nums[i-1]).
        # Example: [1, 4, 2] -> change 4 to 2
        if i < 2 or nums[i] >= nums[i-2]:
          nums[i-1] = nums[i]
        # Otherwise, we must raise the current element (nums[i]).
        # Example: [3, 4, 2] -> change 2 to 4
        else:
          nums[i] = nums[i-1]
          
    return True

Step 4: Always Deliver a Solution (Discussing Trade-offs)

The solution I've provided runs in O(n) time because it involves a single pass through the array. The space complexity is O(1) as I'm only using a few variables. This is very efficient.

"I could have considered a brute-force approach where I try changing every single element one by one and, for each change, check if the entire array is sorted. That would be O(n^2), which would be too slow given the constraint of 10,000 elements. My current single-pass solution is much more optimal."

Step 5: Test Your Work (Verify With Examples)

"Great, the code is written. Now I'd like to test it with a few examples to be sure it works."

• Case [4, 2, 3]:
  • i=1: nums[1] (2) < nums[0] (4). A dip! modifications becomes 1.
  • Check the logic: i < 2 is true. So we lower nums[0] to 2. The array conceptually becomes [2, 2, 3].
  • Loop continues. No more dips. Return true. Correct.
• Case [4, 2, 1]:
  • i=1: nums[1] (2) < nums[0] (4). A dip. modifications becomes 1.
  • Logic: i < 2 is true. Lower nums[0] to 2. Array becomes [2, 2, 1].
  • i=2: nums[2] (1) < nums[1] (2). Another dip! modifications becomes 2.
  • modifications > 1 is now true, so we immediately return false. Correct.
• Edge Case [3, 4, 2, 3] (from my own thinking):
  • i=1: 4 > 3. OK.
  • i=2: nums[2] (2) < nums[1] (4). Dip! modifications becomes 1.
  • Logic: i < 2 is false. Check nums[i] >= nums[i-2]. nums[2] (2) is NOT >= nums[0] (3).
  • So we go to the else block: raise nums[i]. nums[2] becomes 4. Array is now [3, 4, 4, 3].
  • i=3: nums[3] (3) < nums[2] (4). Dip! modifications becomes 2.
  • Return false. Correct.

The code handles the cases correctly. By walking through my own complex test case, I show a deeper level of care for quality.

By following these five keys, I didn't just solve a problem. I showcased a professional engineering process from start to finish. This is how you go from being just another candidate to being the person they know they need to hire.