Day #6/50 of Learning DSA

After an exhilarating weekend at hackCBS8.0, where I had the opportunity to compete alongside over 500 talented hackers, I'm back to share my progress in learning Data Structures and Algorithms. Despite the intense competition, my team and I made it to the finals and proudly secured the MLH Track prize. Although I couldn't post updates over the past two days due to the hackathon, I'm excited to dive back into my learning journey. Today, I tackled the challenges of solving the Rotate Array and Missing Number problems. During the hackathon, I also managed to solve Water Bottles and Remove Duplicates from Sorted Array. Let's explore these problems and the approaches I used to solve them.

Rotate Array:

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Brute Force Approach: Although this was not accepted due to the size of input constraint, this is very intuitive and helpful for understanding.

• Shift each element of the array to right by one.

• Repeat this process k (number of steps) times.

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();

        for(int i=0; i<k; i++){
            int temp = nums[n-1];
            for(int j=n-1; j>=0; j--){
                if(j==0){
                    nums[j] = temp;
                } else {
                    nums[j] = nums[j-1];
                }
            }
        }
    }

Better Approach:

• Copy the elements of the given array in a new array with a given shift factor k.

• Re-copy the elements from temporary array to the original array nums.

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        int arr[n];

        for ( int i = 0; i < n; i++ ){
            arr[ (i+k) % n ] = nums [i];
        }
        for (int i = 0; i < n; i++){
            nums[i] = arr[i];
        }
    }

Missing Number:

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Approach:

• Take an auxiliary array and mark (with 1) the index at by their respective the elements present in the array nums.

• Search for the element or index where 0 is located and the index i the missing element.

    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int arr[10001] = {0};

        for(int i=0; i<n; i++){
            arr[nums[i]] = 1;
        }

        for(int i=0; i<=n; i++){
            if(arr[i] == 0) return i;
        }
        return 0;
    }