Easy Array: Leetcode Series-1

This blog will consist of three easy level array problems along with their approaches and solutions. The difficulty of the problem will increase as we step ahead ( judged as per the acceptance rate on leetcode). However, the general level of the problems will come in the easy category only.

You can simply read the problem here and solve it on any compiler or click the Leetcode link. The question and approach will be discussed here along with the solution. Before getting started, it is essential to mention that Leetcode is a hard platform and it takes a lot of time to get good at coding. Simply putting it, literally everyone is a dummy at some point and is trying to level up somehow. It is absolutely normal to not be able to solve questions in the first, or even the 100th go and maybe soon (or so I hope) you would be laughing at the hard problems.

Ques. 1) 1929. Concatenation of Array

Difficulty: Easy, Acceptance: 90.2%

Link: https://leetcode.com/problems/concatenation-of-array/

Problem:

Approach:

Looking at the problem, the first thing that comes to your mind is that you have to copy and paste the elements of a given array twice into another array. As asked, we would have to first create an array called 'ans' with the size of 2n. To further solve the question, we would have to apply a for loop and enter the elements of 'nums' array into the 'ans' array.

If we carefully read the question, we see that we are already given the conditions to put in our code. All we have to do is apply the for loop! The conditions given in question are explained below:

Solution:

Time Complexity: O(n) , Space Complexity: O(n)

class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        int n=nums.size();
        vector<int> ans(2*n); //Declaring array with 2n size
        for(int i=0;i<nums.size();i++)
        {
            ans[i]=nums[i]; //given in question
            ans[i+n]=nums[i]; //given in question
        }
        return ans;
    }
};

Ques 2) 283. Move Zeroes

Difficulty: Easy, Acceptance: 61.5%

Link: https://leetcode.com/problems/move-zeroes/

Problem:

Approach:

Even though, the question is called 'Move Zeroes', we will try to concentrate on the non-zero numbers. Lets suppose we have two pointers (say i and j) traversing the array in a for loop. By using simple if-else conditions, we can simply increment or skip zeros in the loop (using i). However, if we notice a non zero element, we will swap it with the other pointer j. This can be better explained by the given steps below:

Step 1: Create two pointers i=0 and j=0.

Step 2: If an element in the loop is equal to 0, increment i to skip it (i++).

Step 3: Else we swap the values at i and j and then increment both of them. That   is: swap(nums[i],nums[j]); i++; j++;

Step 4: Return nums array.

Solution:

Time Complexity: O(n) , Space Complexity: O(1)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i,j;
        for(i=0,j=0;i<nums.size();){
            if(nums[i]==0) i++;
            else{
                swap(nums[i],nums[j]);
                i++;
                j++;
            }
        }  
    }
};

Ques 3) 88.Merge Sorted Array

Difficulty: Easy, Acceptance: 46.5%

Link: https://leetcode.com/problems/merge-sorted-array/

Problem:

Approach:

When we look at the question, our initial thought must be to replace all zeros present in nums1 array with all the elements present in nums2 array How to do that though? For this, we would have to run a for loop m+n times. As we can see, the number of zeros in nums1 is equal to the number of elements in nums2. Another observation that we can make is that all the zero elements that have to be replaced are kept on the left side of the array, hence we can easily traverse through each of them and remove them one by one. We will then use sort function in STL to arrange array in ascending order. The procedure can be better understood by the points given below:

Step1: Create two pointers i=0 and j=0.

Step2: Create a for loop from i=0 to i=m+n.

Step3: As soon as we have surpassed the size m (required size of nums1), we will allocate values from nums2 to the rest of the elements using j pointer.

Step4: Use sort function in STL to arrange array in ascending order.

Step5: Return nums1 array.

Solution:

class Solution {
public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int j=0;
    for(int i=0;i< m+n;i++){
        if(i>m-1){
            nums1[i] = nums2[j++];
        } 
    }
    sort(nums1.begin(), nums1.end());
}
};

This is all for this blog! You have officially taken the first step of not being a dummy anymore. Keep coding!

Thank you for reading :)