Skip to main content

6. Search Insert Position

easyAsked at Snowflake

Given a sorted array and a target, return the index where the target is or where it would be inserted. Snowflake asks this to test binary-search mechanics — the same primitive used to locate a row by clustering key inside a micro-partition's min/max metadata.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake storage-team uses this to set up the micro-partition-pruning follow-up.
  • LeetCode Discuss (2025-10)— Recurring at Snowflake new-grad screens.

Problem

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4

Examples

Example 1

Input
nums = [1,3,5,6], target = 5
Output
2

Example 2

Input
nums = [1,3,5,6], target = 2
Output
1

Example 3

Input
nums = [1,3,5,6], target = 7
Output
4

Approaches

1. Linear scan

Walk until you find a value >= target.

Time
O(n)
Space
O(1)
function searchInsert(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) return i;
  }
  return nums.length;
}

Tradeoff: Violates the O(log n) constraint. Mention to acknowledge but reject.

2. Binary search (optimal)

Standard binary search but return lo (the insertion point) when not found, instead of -1.

Time
O(log n)
Space
O(1)
function searchInsert(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Tradeoff: Log n, no edge cases for not-found because the loop converges on the insertion point naturally.

Snowflake-specific tips

Snowflake interviewers grade this on whether you write the half-open binary search (hi = nums.length, not nums.length - 1) so the insertion-point case falls out for free. Bonus signal: relate to micro-partition pruning — Snowflake stores min/max per partition, then binary-searches the partition list for which ones overlap the predicate.

Common mistakes

  • Using mid = (lo + hi) / 2 with closed intervals — fails when target is larger than all elements.
  • Forgetting that JavaScript integer arithmetic on (lo + hi) can lose precision for very large arrays — use >>> 1 for unsigned shift.
  • Returning -1 instead of lo when not found.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • Find the first AND last occurrence of target (LC 34).
  • Search in a rotated sorted array (LC 33).
  • How does Snowflake use this to prune micro-partitions?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why half-open intervals [lo, hi)?

They eliminate the off-by-one trap at hi. When lo == hi, you've found the insertion point — no special-case logic needed.

How does Snowflake prune partitions?

Each micro-partition stores min/max for each column. To answer WHERE col = X, the planner binary-searches partition metadata for partitions whose [min, max] contains X.

Practice these live with InterviewChamp.AI

Drill Search Insert Position and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →