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 4: Model Problems February 1, 2023
  • LeetCode Tip 3: A Goal for LeetCode Practice January 25, 2023
  • LeetCode Tip 2: A Sample Problem January 18, 2023
  • LeetCode Tip 1: Why LeetCode? January 11, 2023
  • A Project for 2023 January 4, 2023
  • 2022 in Review: Content Bots December 28, 2022
  • Quora: How Can an Interviewer Effectively Evaluate Multiple Ways of Solving a Coding Problem? December 21, 2022
  • Quora: Is Stack Overflow Giving ChatGPT Too Much Attention? December 14, 2022
  • Quora: Do Interviewers Look Up Solutions to the Coding Questions They Ask? December 7, 2022
  • Quora: How Can One Become an Expert in Competitive Coding? November 30, 2022
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2023 Duncan Smith