Leetcode 35: Search Insert Position

1. Problem Statement (Simple Explanation):

You are given:

A sorted array nums of distinct integers (ascending).
An integer target.

You must:

Return the index of target in nums if it exists.
If not, return the index where target should be inserted to keep the array sorted.

You must use an O(log n) algorithm → binary search.

2. Examples:

Example 1:

Input: nums = [1,3,5,6], target = 5

5 exists at index 2.

Output: 2

Example 2:

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

Sorted insertion position:

1 (index 0) < 2
3 (index 1) > 2 → 2 should go at index 1.

Output: 1

Example 3:

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

7 is greater than all elements, so it would be inserted at index 4 (end of array).

Output: 4

3. Approach – Binary Search for Lower Bound (O(log n)):

We want the smallest index i such that:

nums[i] >= target

If nums[i] == target, that’s the index.
If nums[i] > target, that’s where target should be inserted.
If no such index exists, insertion position is n (length of array).

This is exactly lower bound.

Algorithm (Step-by-Step):

Initialize:

left = 0

right = n - 1

ans = n // default insertion at end

While left <= right:

mid = left + (right - left) / 2.
If nums[mid] >= target:

ans = mid (current candidate position).
Move left: right = mid - 1 to find smaller index.

Else (nums[mid] < target):

Move right: left = mid + 1.

Return ans.

Because values are distinct and sorted, this works for both “find exact” and “insertion position”.

Pseudo-code:

Complexity:

Let n = len(nums):

Time: O(logn)
Space: O(1)

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code:

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog