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. 

Find a Palindromic String in the Array.

Given an array of strings words[], write a program to return the first palindromic string in the array. If there is no such palindromic string present in the given array then return an empty string "".

Palindromic strings are those strings that read the same from left to right and from right to left. Example: radar(alert-passed)

Example: 
Input: words[] = {"abc", "cap", "radar", "racecar", "cook"}
Output: radar
Explanation: The first palindromic string is "radar"

Input: words[] = {"pet", "cable", "code"}
Output: ""
Explanation: There is no palindromic string, so returning an empty string.

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

Approach 1: Brute Force Approach.

In this approach, we are going to check each string in the array one by one if it is a palindrome. If palindrome is found then return it, else return an empty string.

Below is C++ Implementation:

//C++ Program to find Palindromic String
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isPalindrome(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            return false;
        }
    }
    return true;
}

string firstPalindromicString(vector<string>& words) {
    for (string word : words) {
        if (isPalindrome(word)) {
            return word;
        }
    }
    return "";
}

int main() {
    vector<string> words = {"hello", "world", "racecar", "palindrome"};
    string result = firstPalindromicString(words);
    if (result == "") {
        cout << "No palindromic string found." << endl;
    } else {
        cout << "First palindromic string: " << result << endl;
    }
    return 0;
}

Output:

First palindromic string: racecar

• Time Complexity: O(n * m^2), where n is the number of words in the array and m is the length of the longest word. This is because we need to check each word in the array, and for each word, we need to check if it is a palindrome, which takes O(m^2) time.
• Space Complexity: O(1), since we are not using any additional space beyond the input array.

Approach 2: Using Two Pointers.

In this approach, we use two-pointers to compare characters from the beginning and end of each string. If the characters match, move the pointers inwards until they meet in the middle of the string. If the string is a palindrome, return it, otherwise move on to the next string in the array. 

Below is C++ Implementation:

//C++ Code for finding Palindromic String
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isPalindrome(string s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s[i] != s[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

string firstPalindromicString(vector<string>& words) {
    for (string word : words) {
        if (isPalindrome(word)) {
            return word;
        }
    }
    return "";
}

int main() {
    vector<string> words = {"hello", "world", "racecar", "palindrome"};
    string result = firstPalindromicString(words);
    if (result == "") {
        cout << "No palindromic string found." << endl;
    } else {
        cout << "First palindromic string: " << result << endl;
    }
    return 0;
}

Output:

First palindromic string: racecar

• Time Complexity: O(n * m), where n is the number of words in the array and m is the length of the longest word. This is because we need to check each word in the array, and for each word, we need to compare each character from the beginning and end of the word, which takes O(m) time.
• Space Complexity: O(1), since we are not using any additional space beyond the input array.

Approach 3: Using Reverse String.

This approach is to reverse each string in the array and compare it to the original string. If they are equal, the string is a palindrome. Return the first palindrome found, or an empty string if no palindrome is found.

Below is C++ Implementation:

//C++ Code for Palindromic String
#include <iostream>
#include <string>
#include <vector>

using namespace std;
//function to reverse each string
string reverseString(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        char temp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = temp;
    }
    return s;
}

string firstPalindromicString(vector<string>& words) {
    for (string word : words) {
        if (word == reverseString(word)) {
            return word;
        }
    }
    return "";
}

int main() {
    //array of string
    vector<string> words = {"hello", "world", "racecar", "palindrome"};
    //function call
    string result = firstPalindromicString(words);
    
    if (result == "") {
        cout << "No palindromic string found." << endl;
    } else {
        cout << "First palindromic string: " << result << endl;
    }
    return 0;
}

Output:

First palindromic string: racecar

• Time Complexity: O(n * m), where n is the number of words in the array and m is the length of the longest word. This is because we need to check each word in the array, and for each word, we need to reverse it, which takes O(m) time, and then compare it to the original word, which takes another O(m) time.
• Space Complexity: O(1), since we are not using any additional space beyond the input array.

Program to Find Number of Arithmetic Triplets.

Given a zero-based strictly increasing integer array arr[], and a positive integer diff. Write a program to return the number of unique arithmetic triplets.

Condition for Arithmetic Triplets:

• Index i < j < k.
• arr[j] - arr[i] == diff and,
• arr[k] - arr[j] == diff (alert-passed)

Example:
Input: arr[] = {1, 3, 5, 6, 8, 11, 15}, diff = 2
Output: 1
Explanation:
(0, 1, 2) is an arithmetic triplet because 3 - 1 = 2 and 5 - 3 = 2

Input: arr[] = {0, 1, 4, 6, 7, 10}, diff = 3
Output: 2
Explanation:
(1, 2, 4) is an arithmetic triplet because both 7 - 4 = 3 and 4 - 1 = 3.
(2, 4, 5) is an arithmetic triplet because both 10 - 7 = 3 and 7 - 4 = 3.

There are multiple ways to solve this problem and here we will discuss brute-force and optimized solutions so you can get a better understanding of how to approach similar problems. 

Approach 1: Brute Force Approach.

As the given array contains only positive numbers and elements are in sorted order, we can easily solve this problem by using three nested loops and defining the arithmetic triplet condition inside the inner loop.

Below is the C++ Implementation:

//C++ program to find arithmetic triplets
#include<iostream>
using namespace std;

//function definition
int arithmeticTriplet(int arr[], int size, int diff){
    //variable to get the count
    int count = 0;

    for(int i = 0; i < size; i++){
        for(int j = i + 1; j < size; j++){
            for(int k = j + 1; k < size; k++){
                if((arr[j] - arr[i]) == diff && (arr[k] - arr[j]) == diff){
                    count++;
                }
            }
        }
    }
    return count;
}

int main(){
    int arr[] = {0, 1, 4, 6, 7, 10};
    int size = sizeof(arr)/sizeof(arr[0]);

    int diff = 3;

    cout<<arithmeticTriplet(arr, size, diff);

    return 0;
}

Output:

2

• Time Complexity: O(n^3)
• Space Complexity: O(1)

The time complexity of the solution using the above approach is very high which is a good solution for big-size data. We have to think of a better and more optimized solution which we are going to discuss in our next approach.

Approach 2: Using a Hashmap.

Using a hashmap to store unique elements will help us reduce our time complexity. 

Steps to follow:

• Declare an unordered_map to keep track of unique elements of the array that we have seen so far and also initialize a count variable to count the number of arithmetic triplets. 
• Iterate over the given array, for each element arr[i] check if arr[i] - diff and arr[i] - 2*diff are present in our unordered_map, if yes then increase the value of count by 1.
• Insert the correct element arr[i] into the unordered_map so we can use this value to find out more arithmetic triplets.
• Return the count after processing all the elements of the given array.

Below is C++ Implementation:

//C++ code for finding arithmetic triplets
#include <iostream>
#include <unordered_set>
using namespace std;

//function declaration
int countTriplets(int arr[], int n, int diff) {
    unordered_set<int> seen;
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (seen.count(arr[i] - diff) && seen.count(arr[i] - 2 * diff)) {
            count++;
        }
        seen.insert(arr[i]);
    }

    return count;
}

int main() {

    int arr[] = {1, 3, 5, 6, 8, 11, 15};
    //size of array
    int n = sizeof(arr)/sizeof(arr[0]);

    int diff = 2;
    int count = countTriplets(arr, n, diff);
    cout << count << endl;

    return 0;
}

Output:

1

• Time Complexity: O(n) where n is the length of the input array and we only need to loop over the array once.
• Space Complexity: O(n) as we have used unordered_set to keep track of unique elements of the array.