Search Insert Position – Leetcode #35

Problem Statement

This problem is from Leetcode – Search Insert Position. The problem statement is given below:

Given a sorted array and a target, return the target’s index or the insertion index if not found.

Solution

This problem is asking us to figure out the correct index position for a given number in a sorted array. Please note that its asking us only to return the index position and not the updated array.

Approach-1

Lets take a simple one pass O(n) approach.

1. Iterate the given integer array.
2. Compare the given target val with current number in array.
3. If current number is greater than OR equal to the target val, then return this index.
4. Else return the length of the input array as answer

Lets see the code sample below:

/*
	 * function to find the correct index position for given target val
	 * input array -> int[] nums = {1,3,5,6};
	 * target val -> 4
	 */
	public int searchInsert(int[] nums, int target) {
		
		// store array length as default return answer
		int val = nums.length ;
		
		/*
		 * Iterate the given array
		 */
		for(int i=0; i<nums.length; i++) {
			
			// store the current array value in var
			int curNum = nums[i];
			
			/*
			 * check if current array val is equal to or greater than target
			 */
			if(curNum == target || curNum > target) {
				
				// if yes then return this index
				val = i;

				return val;
			}
		}
		
		// else return input array length as answer
		return val;
	}

This code returns the output as below:

Insert position: 2

You can checkout the code from Github here: Search Insert Position – First Approach

PERFORMANCE ANALYSIS

RUNTIME	0 ms | Beats 100.00 %
MEMORY	43.04 MB | Beats 50.49 %
TIME COMPLEXITY	O ( N )