Day 21 problem and solution!

Hello and welcome back brave human being,

Before we dive into today’s problem, let me tell you, I’ve seen your feedback about sharing tips and tricks on cold messaging. Therefore today’s feature guest is the QUEEEEEEN 👑 of cold emailing.

Stay tuned for her tips at the end of this email.

Day 21: 33. Search in Rotated Sorted Array

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Let's set an example…

Input: nums = [4,5,6,7,0,1,2]
target = 0
Output: 4

Let's start slow and linear.

The simplest way to do it would be using a for loop to compare each element and check if it matches our target.

Simple but expensive, since it would have a time complexity of O(N).

Since we are too cheap for that solution, let’s do something quicker, let’s do a binary search.

Let's dive in 🤿 :

The first thing we need to tackle is, how on earth will we know if the array has been rotated at the given comparison???

Well, it took me a bit but it’s simpler than you think.

Let’s start by declaring our variables:

int L = 0 
int R = nums.size() -1 
int middle = (L + R) / 2 

Our stopping condition would be if we found the answer.

if (nums[middle] == target) 
   return middle 

Now, where will go?

Let’s first figure out if the left side of the array is rotated.

If true, where will we go?

If the element to the left is less than our target and less than the element that the middle index is pointing to, it means it’s sorted.

if (nums[L] <= target && target < nums[middle]) 
   R = middle - 1; 
                                          
else 
    L = middle + 1; 
    

Now that we checked the left side is sorted, by default the rest is and you can repeat the same logic.

Let’s look at the complete solution.

class Solution {
public:
    int search(vector<int>& nums, int target) { 
        int L=0; 
        int R = nums.size()-1; 
        while (L<=R){
            int middle = L + (R - L) / 2;
            if(nums[middle]==target){
                return middle; 
            }
            // Check if the left half is sorted
            if (nums[L]<= nums[middle]){ 
                // Target is in the left 
                if (nums[L] <= target && target < nums[middle]) {
                    R = middle - 1; 
                } else {
                    L = middle + 1; 
                }
            }
            // Right side must be sorted! 
            else { 
                // Target is in the right half
                if (nums[R]>=target && target > nums[middle]){
                    L = middle + 1; 
                }
                else {
                    R = middle -1; 
                }
            }
        }
        return -1; 
    }
};

Simpler than we thought right?

Her best tips on how to cold email!

Now let’s send some emails!!!!!

See you Thursday!

Denisse