Program to Left Rotate an Array by K Places.

Given an integer array arr[] of size n, the task is to rotate the array to the left by K steps, where K is a non-negative number.

Example:

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}  K = 3
Output: arr[] = {4, 5, 6, 7, 8, 1, 2, 3}

Input: arr[] = {4, 6, 1, 5, 2, -2}  k = 2
Output: arr[] = {1, 5, 2, -2, 4, 6}

There are multiple approaches to rotating an array and here we are going to discuss each of them one by one in detail.

Key Note: When the number of rotations (K) is greater than the size of the array (n) for a left rotation, we can handle it by taking the effective number of rotations, which is K % n. This is because, after every n rotation, the array comes back to its original position. So, rotating by K % n is equivalent to rotating by K. (alert-passed)

Approach 1: Brute Force Approach.

This approach takes a straightforward but less efficient approach. It involves repeatedly shifting the entire array to the left by one position K times. While conceptually simple, this method has a time complexity of O(n * k), making it less suitable for large arrays or a high number of rotations.

Step-by-step algorithm:

• Store the first element in a temporary variable.
• Shift all elements in the array to the left by one position.
• Place the temporary variable at the end of the array.
• Repeat steps 1-3 for K times.

Below is the C++ code implementation of the above approach:

// C++ code to left rotate array by k position 
#include <iostream>
using namespace std;

// function to left rotate an array
void rotateLeftBruteForce(int arr[], int n, int k) {
    for (int i = 0; i < k; ++i) {
        int temp = arr[0];
        for (int j = 1; j < n; ++j) {
            arr[j - 1] = arr[j];
        }
        arr[n - 1] = temp;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    rotateLeftBruteForce(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

3 4 5 6 7 1 2

• Time Complexity: O(n * k) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

• Space Complexity: O(1) no extra space is required to solve this problem using the above approach.

Approach 2: Using Extra Space.

In this approach, an auxiliary array is utilized to store the first K elements of the original array. The remaining elements are then shifted to the left in the original array, and the elements from the auxiliary array are placed at the end.

Step-by-step algorithm:

• Create an auxiliary array of size K.
• Copy the first K elements of the original array to the auxiliary array.
• Shift the remaining elements in the original array to the left by K positions.
• Copy the elements from the auxiliary array to the end of the original array.

Below is the C++ code implementation for the above approach:

// C++ code to left rotate an array using extra space
#include <iostream>
using namespace std;

void rotateLeftExtraArray(int arr[], int n, int k) {
    // Check for the case where k is greater than n
    k = k % n;

    // Create an auxiliary array
    int temp[k];

    // Copy the first k elements to the auxiliary array
    for (int i = 0; i < k; ++i) {
        temp[i] = arr[i];
    }

    // Shift the remaining elements 

    // in the original array to the left
    for (int i = k; i < n; ++i) {
        arr[i - k] = arr[i];
    }

    // Copy the elements from the auxiliary array 

    // to the end of the original array
    for (int i = 0; i < k; ++i) {
        arr[n - k + i] = temp[i];
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    rotateLeftExtraArray(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

4 5 6 7 1 2 3

• Time Complexity: O(n) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

• Space Complexity: O(k) k is the size of an auxiliary array that is used in the above algorithm to rotate the array.

Approach 3: Reversal Algorithm.

The Reversal Algorithm reverses specific segments of the array to achieve rotation. First, it reverses the first K elements, then the remaining elements, and finally the entire array. 

Step-by-step algorithm:

• Reverse the first K elements of the given array.
• Reverse the remaining elements of the given array.
• Reverse the entire array.

Illustration:

Below is the C++ code implementation for the above approach:

// C++ code to left rotate an array using reversal method
#include <iostream>
using namespace std;

// function to reverse array
void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        std::swap(arr[start], arr[end]);
        ++start;
        --end;
    }
}

// function to left rotate array
void rotateLeftReversal(int arr[], int n, int k) {
    // Check for the case where k is greater than n
    k = k % n;

    // Reverse the first k elements
    reverseArray(arr, 0, k - 1);

    // Reverse the remaining elements
    reverseArray(arr, k, n - 1);

    // Reverse the entire array
    reverseArray(arr, 0, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    rotateLeftReversal(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

4 5 6 7 1 2 3

• Time Complexity: O(n) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

• Space Complexity: O(1) as no extra space is required to resolve the problem.

Approach 4: Juggling Algorithm.

The Juggling Algorithm is an optimization over the reversal method. It uses the concept of finding the greatest common divisor (gcd) of n and k. It then iterates through sets of elements that need to be rotated together, reducing the number of swaps needed.

Step-by-step algorithm:

• Find the greatest common divisor (gcd) of n and k.
• Iterate through each set of elements that need to be rotated together.
• Use temporary variables to swap elements within each set.

Below is the C++ code implementation for the above approach:

// C++ code to rotate array using juggling algorithm
#include <iostream>
using namespace std;

// function to find gcd
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// function to left rotate array
void rotateLeftJuggling(int arr[], int n, int k) {
    // Check for the case where k is greater than n
    k = k % n;

    // Find the greatest common divisor (gcd) of n and k
    int sets = gcd(n, k);

    for (int i = 0; i < sets; ++i) {
        int temp = arr[i];
        int j = i;

        while (true) {
            int d = (j + k) % n;
            if (d == i) {
                break;
            }
            arr[j] = arr[d];
            j = d;
        }

        arr[j] = temp;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    rotateLeftJuggling(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

4 5 6 7 1 2 3

• Time Complexity: O(n) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

• Space Complexity: O(1) as no extra space is required.

These are the few algorithms to left rotate an array by K position and you can choose one which is best for your requirement.

Constructor and Destructor in C++.

Constructor and Destructor in C++ are the special member functions of the class and they are essential components of Object Oriented Programming. Constructors are special functions within a class that initialize the object when it is created, providing default or custom values to its attributes. On the other hand, destructors are used to clean up resources allocated by the object during its lifetime, and they are automatically invoked when the object goes out of scope or is explicitly deleted.

What is a Constructor in C++?

A constructor in C++ is a special member function of a class that is automatically invoked when an object of that class is created. Its primary purpose is to initialize the object's attributes or perform any necessary setup. Constructors have the same name as the class and do not have a return type. 

There are many types of constructors available in C++. When an object is instantiated, the appropriate constructor is automatically called, ensuring that the object is properly initialized before it is used. Constructors play a crucial role in object-oriented programming by establishing the initial state of objects.

How many types of constructors in C++?

There are basically four types of constructors present in C++ and these are:

• Default Constructor.
• Parameterized Constructor.
• Copy Constructor.
• Dynamic Constructor.

Let's discuss each of them in detail one by one,

Default Constructor.

A default constructor in C++ is a constructor that takes no parameters. It is automatically generated by the compiler if no constructor is explicitly defined in the class. It is called when an object is created with no arguments.

Syntax:

class ClassName {
public:
    ClassName() {
        // Constructor code
    }
};

Example Code for Default Constructor:

// C++ code implementation for default constructor
#include <iostream>
using namespace std;

class MyClass {
private:
    int rollNo;
    string name;

public:
    // Default Constructor
    MyClass() {
        std::cout << "Default Constructor Called" << std::endl;
        rollNo = 0;
        name = "NULL";
    }

    void display(){
        cout << "Student Name: " << name << endl;
        cout << "Roll No: " << rollNo << endl;
    }
};

int main() {
    // Creating an object invokes the default constructor
    MyClass obj;  

    obj.display();
    return 0;
}

Output:

Default Constructor Called
Student Name: NULL
Roll No: 0

In the above example, we created a class MyClass with a default constructor to initialize the initial values to data members of the class, and the default constructor is called as soon as we create the object of that class obj. 

Note: It's important to explicitly define a default constructor when custom initialization is required or when other constructors are defined in the class. (alert-passed)

Parameterized Constructor.

A parameterized constructor in C++ is a constructor that accepts parameters during its invocation. It allows you to initialize the object with specific values based on the provided arguments. 

Syntax:

class ClassName {
public:
    ClassName(type1 param1, type2 param2, ...) {
        // Constructor code
    }
};

Example Code for Parameterized Constructor:

// C++ code implementation for Parameterized constructor
#include <iostream>
using namespace std;

class Car {
private:
    string brand;
    int year;

public:
    // Parameterized Constructor
    Car(string b, int y) {
        cout << "Parameterized Constructor Called" << endl;
        brand = b;
        year = y;
    }

    void display() {
        cout << "Brand: " << brand << ", Year: " << year << endl;
    }
};

int main() {
    // Creating an object using the parameterized constructor
    Car myCar("Toyota", 2022);
    myCar.display();  
    return 0;
}

Output:

Parameterized Constructor Called
Brand: Toyota, Year: 2022

In the above example, the parameterized constructor takes parameters (in this case, a string and an integer) during its declaration. The constructor is called when an object is created, allowing custom initialization based on the provided arguments.

Copy Constructor.

A copy constructor in C++ is a special type of constructor that is used to create a new object as a copy of an existing object of the same class. It is invoked when an object is passed by value or returned by value.

Note: If a copy constructor is not explicitly defined, the compiler generates a default copy constructor. (alert-success)

Syntax:

class ClassName {
public:
    // Copy Constructor
    ClassName(const ClassName& obj) {
        // Constructor code
    }
};

Example Code for Copy Constructor:

// C++ code implementation for Copy constructor
#include <iostream>
using namespace std;

class Student {
private:
    string name;
    int age;

public:
    // Parameterized Constructor
    Student(string n, int a) : name(n), age(a) {
        cout << "Parameterized Constructor Called" << endl;
    }

    // Copy Constructor
    Student(const Student& obj) : name(obj.name), age(obj.age) {
        cout << "Copy Constructor Called" << endl;
    }

    void display() {
        cout << "Name: " << name << ", Age: " << age << endl;
    }
};

int main() {
    // Creating an object using the parameterized constructor
    Student originalStudent("John", 20);
    originalStudent.display();  

    // Creating a new object using the copy constructor
    Student copiedStudent = originalStudent;
    copiedStudent.display();  
    
    return 0;
}

Output:

Name: John, Age: 20
Copy Constructor Called
Name: John, Age: 20

In the above example, the copy constructor takes a reference to an object of the same class (const ClassName& obj) as its parameter. It initializes the members of the new object with the values of the corresponding members of the existing object.

Dynamic Constructor.

In C++, a dynamic constructor is not a distinct type of constructor. Constructors are typically classified based on their parameters and use cases, such as default constructors, parameterized constructors, and copy constructors. However, there might be a misunderstanding or miscommunication about the term "dynamic constructor."

If you are referring to dynamic memory allocation within a constructor (e.g., using new), this is a common practice in C++ but doesn't give rise to a separate category of a constructor. 

What is a Destructor in C++?

A destructor in C++ is a special member function of a class that is executed whenever an object of the class goes out of scope or is explicitly deleted. It is used to release resources or perform cleanup operations associated with the object before it is destroyed.

Syntax:

class ClassName {
public:
    // Constructor(s)
    ClassName(); // Default constructor
    ClassName(parameters); // Parameterized constructor

    // Destructor
    ~ClassName(); 
};

Key points about Destructor:

• A destructor has the same name as the class but is prefixed with a tilde (~).
• Unlike constructors, which can be overloaded, a class can have only one destructor.
• The destructor is automatically invoked when an object goes out of scope or is explicitly deleted.
• It is used for releasing resources, closing files, releasing memory, or performing any cleanup necessary before the object is destroyed.

Example Code for Destructor in C++:

// C++ code implementation for Destructor
#include <iostream>
using namespace std;

class MyClass {
public:
    // Constructor
    MyClass() {
        std::cout << "Constructor Called" << std::endl;
    }

    // Destructor
    ~MyClass() {
        std::cout << "Destructor Called" << std::endl;
    }
};

int main() {
    // Creating an object
    MyClass obj; 

    // Object goes out of scope, destructor is called
    return 0;
}

Output:

Constructor Called
Destructor Called

Note: In the example, the destructor prints a message for demonstration purposes. In real-world scenarios, destructors are often used to deallocate memory, close files, or release other resources.(alert-passed)

 (getButton) #text=(Access Specifiers in C++) #icon=(link) #color=(#2339bd)

Program to Move All Zeroes to the End of Array.

Given an integer array arr[] of size n, the task is to move all zeroes (0's) to the end of the array while maintaining the relative order of non-zero elements.

Example:

Input: arr[] = {0, 1, 0, 3, 5, 0}
Output: arr[] = {1, 3, 5, 0, 0, 0}

Input: arr[] = {0, 1}
Output: arr[] = {1, 0}

There are multiple approaches to solving this problem. Let's discuss each approach one by one from brute force to optimized one.

Approach 1: Brute Force Approach.

This is a basic approach in which we are going to traverse the complete array to store all non-zero elements in the front of the new array and add the required number of zeroes at the end. Below are the steps to follow: 

• Create a new array.
• Iterate through the original array.
• For each non-zero element, add it to the new array.
• After completing the iteration, add the required number of zeros to the new array.
• The new array will now have all non-zero elements followed by zeros.

Below is the C++ code implementation for the above approach:

//C++ code to move all zeroes at the end of array
#include <bits/stdc++.h>
using namespace std;

vector<int> moveZeroesBruteForce(vector<int>& arr) {
    vector<int> result;

    for (int i : arr) {
        if (i != 0) {
            result.push_back(i);
        }
    }
    //count of 0's present in the array
    int numberOfZeroes = arr.size() - result.size();
    result.insert(result.end(), numberOfZeroes, 0);

    return result;
}

int main(){
    vector<int> arr = {0, 1, 0, 3, 4, 0, 0, 8};

    vector<int> ans = moveZeroesBruteForce(arr);

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] <<" ";
    }

    return 0;
}

Output:

1 3 4 8 0 0 0 0 

• Time Complexity: O(n) where n is the number of elements present in the array.

• Space Complexity: O(n) where n is the number of elements present in the array.

Approach 2: Optimized Approach. 

This is an in-place approach in which we are not going to use any extra space to move all 0s to the end of the array. Below are the steps to follow:

• Initialize a variable to keep track of the position to overwrite.
• Iterate through the array.
• For each non-zero element, overwrite the next position with the current element.
• After completing the iteration, fill the remaining positions with zeros.
• The array will now have all non-zero elements followed by zeros. 

Below is the C++ code implementation for the above approach:

//C++ code to move all zeroes at the end of array
//In-place approach
#include <bits/stdc++.h>
using namespace std;

vector<int> moveZeroesOptimized(vector<int>& arr) {
    int writeIndex = 0; // Position to overwrite

    for (int i : arr) {
        if (i != 0) {
            arr[writeIndex++] = i;
        }
    }

    // Fill the remaining positions with zeros
    while (writeIndex < arr.size()) {
        arr[writeIndex++] = 0;
    }

    return arr;
}

int main(){
    vector<int> arr = {0, 1, 0, 3, 4, 0, 0, 8};

    vector<int> ans = moveZeroesOptimized(arr);

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] <<" ";
    }

    return 0;
}

Output:

1 3 4 8 0 0 0 0 

• Time Complexity: O(n) where n is the number of elements present in the array.

• Space Complexity: O(1) as no extra space is required to solve the problem using this approach.

Approach 3: Two Pointer Approach.

In this approach, we use two pointers, one to iterate through the array and the next the keep track of position for non-zero values. Below are the steps that need to be followed:

• Use two pointers - one to iterate through the array and another to keep track of the position to overwrite.
• Iterate through the array.
• For each non-zero element, swap it with the element at the position to overwrite.
• After completing the iteration, the array will have all non-zero elements followed by zeros.

Below is the C++ code implementation for the above approach:

//C++ code to move all zeroes at the end of array
//In-place two pointer approach
#include <bits/stdc++.h>
using namespace std;

vector<int> moveZeroesTwoPointer(vector<int>& arr) {
    int writeIndex = 0; // Position to overwrite

    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] != 0) {
            std::swap(arr[writeIndex++], arr[i]);
        }
    }

    return arr;
}

int main(){
    vector<int> arr = {0, 1, 0, 3, 4, 0, 0, 8};

    vector<int> ans = moveZeroesTwoPointer(arr);

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] <<" ";
    }

    return 0;
}

Output:

1 3 4 8 0 0 0 0 

• Time Complexity: O(n) where n is the number of elements present in the array.

• Space Complexity: O(1) as no extra space is required to solve the problem using this approach.

I hope you understood all three approaches to solving this problem of moving 0s to the end of the given array. 

Program to Remove Duplicate From Sorted Array in C++.

Given an integer array arr[] sorted in ascending order, the task is to remove duplicate elements such that the relative order of the elements should be kept the same. 

Example:

Input: arr[] = {1, 1, 2, 2, 2, 3}
Output: arr[] = {1, 2, 3}

Input: arr[] = {1, 2, 5, 5}
Output: arr[] = {1, 2, 5}

There are multiple ways to solve this problem, let's discuss each of them one by one:

Approach 1: Brute Force Approach.

It is the simplest approach in which we are going to use extra space to store only unique elements. Below are the steps to follow:

• Create a new array temp[].
• Iterate through the original array arr[].
• For each element, check if it is already present in the new array.
• If not, add it to the new array.
• The new array contains elements without duplicates.

At the end, you can copy the elements of the new array into the original array and return the original array.

Note: In the below code we have used std::vector() instead of the array because in real-world problems and in interviews we have to deal with vectors.   

Example Code: Below is the C++ code implementation for the above approach.

//C++ code to remove duplicate elements from the array
#include <bits/stdc++.h>
using namespace std;

int removeDuplicatesBruteForce(vector<int>& arr) {
    vector<int> result;

    for (int i : arr) {
        //checking if element already exist
        if (find(result.begin(), result.end(), i) == result.end()) {
            result.push_back(i);
        }
    }
    arr = result;
    return result.size();
}

int main(){
    vector<int> arr = {1, 1, 2, 2, 2, 3, 5};

    int n = removeDuplicatesBruteForce(arr);

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

    return 0;
}

Output:

1 2 3 5

• Time Complexity: O(n^2) where n is the number of elements in the array.

• Space Complexity: O(n) where n is the number of elements in the array.

Approach 2: Optimized Approach.

In this approach, we are going to iterate the complete array only once to find all unique elements. Below are the steps to be followed:

• Create a result vector and add the first element of the array.
• Iterate through the original array from the second element.
• For each element, check if it is equal to the previous element.
• If not, add it to the result vector.
• The result vector will now contain elements without duplicates.

Example Code: Below is the C++ code implementation for the above approach.

//C++ code to remove duplicate elements from the array
#include <bits/stdc++.h>
using namespace std;

int removeDuplicatesOptimized(vector<int>& arr) {
    vector<int> result;

    if (!arr.empty()) {
        //add first element to array
        result.push_back(arr[0]);

        for (size_t i = 1; i < arr.size(); ++i) {
            //check if element is equal to previous element
            if (arr[i] != arr[i - 1]) {
                result.push_back(arr[i]);
            }
        }
    }
    //copy unique elements to original array
    arr = result;
    return result.size();
}

int main(){
    vector<int> arr = {1, 1, 2, 2, 2, 2, 5};

    int n = removeDuplicatesOptimized(arr);

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

    return 0;
}

Output:

1 2 5

• Time Complexity: O(n) where n is the number of elements in the array.

• Space Complexity: O(n) where n is the number of elements in the array.

Approach 3: Two Pointer Approach.

In this approach, we are not going to use any extra space to solve the problem instead we are going to use an in-place approach. Below are the steps to follow:

• Use two pointers - one to iterate through the array and another to keep track of the position to overwrite.
• Iterate through the array from the second element.
• If the current element is different from the previous one, overwrite the next position with the current element.
• The array up to the position of the second pointer will now contain elements without duplicates.

By completing the above steps all unique elements will move from the given vector (array) and then you can resize the vector up to the last overwrite position.

Note: We are starting the iteration from 1 because the element at position 0 is always unique and it does not require any replacement.

Example Code: Below is the C++ code implementation for the above approach.

//C++ code to remove duplicate elements from the array
//In-place approach
#include <bits/stdc++.h>
using namespace std;

int removeDuplicatesInPlace(vector<int>& arr) {

    int writeIndex = 1; // Position to overwrite

    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] != arr[i - 1]) {
            arr[writeIndex++] = arr[i];
        }
    }

    // Resize the array to the size of unique elements
    arr.resize(writeIndex);
    return arr.size();
}

int main(){
    vector<int> arr = {0, 1, 1, 2, 2, 2, 2, 4, 5, 5};

    int n = removeDuplicatesInPlace(arr);

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

    return 0;
}

Output:

0 1 2 4 5

• Time Complexity: O(n) where n is the number of elements in the array.

• Space Complexity: O(1) in-place modification is performed so no extra space is required.

So these are the three different approaches to removing duplicate elements from a sorted array.