The Mix Tape - Leetcode Series 3

Welcome back Dummies! On today's blog, we will be exploring medium level problems of Linear Data Structures on Leetcode. The flow of this blog remains the same! First we will go through each problem statement and discuss the intuition and next up, we will be jumping to hands on code.

The pre requisites of this particular blog is basic knowledge of Linear Data Structures such as Arrays, Linked List etc along with knowledge of searching techniques (like Binary Search). Let the coding begin.

Problem : 33 - Search in Rotated Sorted Array

Link: https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Brute Force/ Dummy Approach:

Just go ahead and apply Linear search. Why bother? Create a for loop traversing each element and find the element you need.

class Solution {
public:
    int search(vector<int>& nums, int target) {
     for(int i =0;i<nums.size();i++)
     {
        if(nums[i] == target) return target;
     }
    return -1;
    }
  };

Space: O(1)

Time: O(n)

Since we are using more time than the mentioned limit (O(logn)), we would have to move on t0 a better approach.

Better Approach :

Apply Binary Search! This can be done through the steps mentioned below-

In the given question, we can see that there may be a pivot point in the array. To make sure that binary search can be applied, we break down the question into 3 simple conditions:

1. If array is rotated and nums[mid]>nums[end]
2. If the array is rotated and nums[mid]>nums[start]
3. If the array is sorted without rotation.

All these steps are further broken down to two conditions each that helps us find the exact position for target.

For Example: Step 1), if nums[mid]>nums[end], then we further check position of target to see if it lies between mid and end or start and end and proceed by applying binary search accordingly.

In 3)Step, we can apply normal binary search since the array is sorted. If target is not found with the help of all these steps, simply return -1.

Code:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start=0;
        int end= nums.size()-1;
        while(start<=end){
            int mid=(start+end)/2;
            if(target==nums[mid]) return mid;
            if(nums[mid]>nums[end]){
                if(target<nums[mid] and target>=nums[start])
                      end=mid-1;
                else start= mid+1;
            }
            else if(nums[mid]<nums[start])
            {
                if(target>nums[mid] and target<= nums[end])
                     start=mid+1;
                else end=mid-1;
            }
            else{
                if(target<nums[mid]) end=mid-1;
                else start=mid+1;
            }
        }
        return -1;
    }
};

Problem: 1637 - Widest Vertical Area Between Two Points Containing No Points

Link:https://leetcode.com/problems/widest-vertical-area-between-two-points-containing-no-points/description/

Approach:

If we look at our test cases carefully, we could conclude that the question is basically asking the maximum distance possible between any two points.

We can ignore the fact that area is mentioned in the question and try to look at in the way that several points on X-axis are given and we have to find the largest possible distance between any two points. For this, the following steps can be followed:

1) Declare a vector to store integers.
2) Add elements of X-axis only to the new vector (only they are required for our solution)
3) Sort the points of X-axis present in our vector.
4) Store and return the value of maximum distance between any two points.

Code:

class Solution {
public:
    int maxWidthOfVerticalArea(vector<vector<int>>& points) {
    
        int size = points.size();
        int maximum = 0;
        vector<int> sort_vec; //taking a new vector to obtain sorted elements
        
        for(int i=0;i<size;i++)
        {
            sort_vec.push_back(points[i][0]); 
            //because only x axis integers are required for ans 
        } 
        
        sort(sort_vec.begin(),sort_vec.end()); //sorting 
        
        for(int i=1;i<size;i++)
        {
           maximum=max(maximum, sort_vec[i]-sort_vec[i-1]);
           // stores value of maximum distance in maximum
        }
        
        return maximum;

    }
};

Problem: 328- Odd Even Linked List

Link:https://leetcode.com/problems/odd-even-linked-list/description/

Approach:

To solve this problem in an easy way, one can follow the following steps:

1) Create a pointer named 'odd' pointing to the head and ultimately to all odd numbered nodes.

2) Again, create a pointer names 'even' pointing to the node which is next to the head (head->next) and ultimately points to all even Nodes.

3) Run a loop which helps join all the odd and even nodes.

4) Create another pointer called 'joint' which also points to head->next.

5) Once all the odd and even nodes are joined, join them together by pointing the odd->next to joint.

6) Return Head.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        //edge case 
        if(head==NULL or head->next ==NULL or head->next->next==NULL )
         return head;

        //declaring pointers
        ListNode* odd=head;
        ListNode* even= head->next;
        ListNode* joint=head->next;
        
        //loop for joining all odds to odds and evens to evens
        while(odd->next and even->next)
        {
            odd->next=odd->next->next;
            even->next=even->next->next;
            odd=odd->next;
            even=even->next;
        }
        // join end of odd nodes to start of even nodes
        odd->next=joint;
        return head;
    }
};

And with this, we have finally come to the end of our blog!

Keep coding Dummies!