Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

LeetCode Tip 2: A Sample Problem

By Duncan Smith Jan 18 0

LeetCode 2023

To help make the upcoming tips less abstract, I’m going to start with a sample problem that I’ll refer to when needed: LeetCode problem 704, Binary Search. I chose binary search because it has a short implementation that uses only basic language features, but even experts have trouble getting it right.

In Problem 704, you are given an array of integers nums sorted in ascending order, and an integer target. You must implement a function that returns the array index of target, or -1 if nums does not contain target.

When you need to search a sorted array, binary search should be the first approach that comes to mind. The idea is to start in the middle, check which half contains the target, and repeat the search in that half. Keep doing this until you find the target or you get down to one element that isn’t the target.

Here is an iterative implementation that will work with minor changes in any C-style language:

    public int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length-1;

        while (lo <= hi) {
            int mid = lo+(hi-lo)/2;

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] < target) {
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }

        return -1;
    }

lo and hi are the endpoints of the section we’re currently searching, starting with the first and last elements of the array. mid is the middle of the range, calculated in a way that avoids the overflow bug that infamously tripped up the experts. If the target is at position mid, we’re done. If it isn’t at position mid, it must be higher than mid, lower than mid, or not found in nums. If we exit the loop without finding target, that means it isn’t in the array.

The tricky part of this implementation, besides the overflow bug, is the loop condition. What is it about the behavior of lo and hi that guarantees that if we ever reach the point where lo > hi, we know that the target is not found?

I won’t go into the mathematical argument here (consult Sedgewick or Knuth for details). But the intuition is that on each iteration of the while loop, we either return mid, increase lo by 1, or decrease hi by 1. There is no case where a loop iteration results in lo decreasing, hi increasing, or neither variable changing. The variables are always moving towards each other. Therefore, if we don’t find the target, lo must eventually increase to or beyond the value of hi, or hi must eventually decrease to or below the value of lo. This guarantees that the loop will terminate if target is not found.

This year, I’m publishing a series of tips for effective LeetCode practice. To read the tips in order, start with A Project for 2023

Categories: LeetCode

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • 2022 in Review: Content Bots
  • 2021 in Review: Thoughts on Solving Programming Puzzles
  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • LeetCode Tip 11: How To Use Spaced Repetition (Part 1) March 22, 2023
  • LeetCode Tip 10: Planning a Spaced Repetition Schedule March 15, 2023
  • Book Review – Algorithmic Thinking: A Problem-Based Introduction, Second Edition March 9, 2023
  • LeetCode Tip 9: Spaced Repetition March 8, 2023
  • LeetCode Tip 8: Anatomy of a Model Solution March 1, 2023
  • LeetCode Tip 7: How to Write a Model Solution February 22, 2023
  • LeetCode Tip 6: Model Solutions February 15, 2023
  • LeetCode Tip 5: Choosing a Model Problem February 8, 2023
  • LeetCode Tip 4: Model Problems February 1, 2023
  • LeetCode Tip 3: A Goal for LeetCode Practice January 25, 2023
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2023 Duncan Smith