Search for a command to run...
Hi, Nice seeing you here I am a Software Engineer with a background in Computer Science having in-depth knowledge of Backend Development, Frontend Development and DevOps. I Love building and deploying systems with my knowledge and create a product that is easily accessible to all. Really appreciate your time.
No comments yet. Be the first to comment.
Welcome to my blog series on algorithms! In this series, we will be diving deep into the world of algorithms and exploring various concepts related to them.
Given an array of N integers return an element that occurs more than N/2 times in the given array. The Brute Force The most Navie and brute force approach is - Loop through each of the elements of the array For each of the elements, find its count ...
STEP 0 : Creating an empty Nodejs repository Go to your desired directory and run the below command to setup an empty directory with package.json npm init -y STEP 1: Creating a server To create an express server we have to install express STEP 1.1: ...
What is a Middleware ? In Backend development middleware is the code snippet that resides before the server and the main purpose of a middleware is to filter out the request that does not perform a specific criteria which is written on the middleware...
Authentication is the process of verifying the identity of a user or entity attempting to access a system or resource. It is a fundamental aspect of security in web development and is essential for ensuring that only authorized individuals or entitie...
STEP 0: Creating an empty Nodejs repository Go to your desired directory and run the below command to setup an empty directory with package.json npm init -y STEP 1: Creating a server To create an express server we have to install express STEP 1.1: I...
Given an array of N integers return an element that occurs more than N/2 times in the given array. The Brute Force The most Navie and brute force approach is - Loop through each of the elements of the array For each of the elements, find its count ...
you must be wondering, why is this even a question
isn't it inherent that we can just sort it, by maybe using some inbuilt function or maybe any of the sorting techniques?
Okay, so let me rephrase my question -
Let's begin solving the problem using the brute-force approach, which is just sorting the array by a sorting technique.
since the most optimized sorting technique is merge sort, so we will be using that.
#include<iostream>
#include<vector>
using namespace std;
void merge(int arr[], int low, int mid, int high) {
int left = low;
int right = mid + 1;
vector<int> temp;
while(left <= mid && right <= high) {
if (arr[left] < arr[right]) {
temp.push_back(arr[left]);
left++;
} else {
temp.push_back(arr[right]);
right++;
}
}
while(left <= mid) {
temp.push_back(arr[left]);
left++;
}
while(right <= high) {
temp.push_back(arr[right]);
right++;
}
for (int i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
}
void mergeSort(int arr[], int low, int high) {
if (low >= high) return;
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
int main() {
int arr[] = {0,1,0,2,0,0,1,2,2,1,2,1,0};
mergeSort(arr, 0, 13);
for (int i = 0; i < 13; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
The time complexity for the brute force approach comes out to be O(NLogN).
It can be more optimized by observing the fact that we only have three types of numbers in the array, and if we can maintain the count of each of them then that can be used to overwrite the array.
#include<iostream>
using namespace std;
int main() {
int arr[] = {0,1,0,2,0,0,1,2,2,1,2,1,0};
int count0 = 0, count1 = 0, count2 = 0;
// counting the count of 0s, 1s and 2s and storing in different
// variables
for (int i = 0; i < 13; i++) {
if (arr[i] == 0) count0++;
else if (arr[i] == 1) count1++;
else count2++;
}
// replacing the starting elements with 0s
for (int i = 0; i < count0; i++) {
arr[i] = 0;
}
// replacing the middle elements with 1s
for (int i = count0; i < count1 + count0; i++) {
arr[i] = 1;
}
// replacing the end elements with 2s
for (int i = count1 + count0; i < 13; i++) {
arr[i] = 2;
}
for (int i = 0; i < 13; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
The time complexity for the better approach comes out to be O(2N).
We can write the most optimized code by using Dutch National Flag Algorithm. Let's understand what it is -
Let's take three variables - low, mid, and high.
These variables will be diving the array into 4 parts -
0 .... low - 1: contains all 0s
low .... mid - 1: contains all 1s
mid ..... high: not sorted
high + 1 ..... N - 1: contains all 2s
so in starting since the array is not sorted, so the first element of the array would be treated as mid and the last element as high.
Now what we have to do is to perform specific operations on a specific number that we encounter -
0: if we encounter 0, then we will swap it with low because 0 to low - 1 are 0s, and we have to, place all 0s together. By doing that, we will also increase the value of low and mid
1: if we encounter 1, we won't be doing anything because it is at its correct position, we will only increase the value if mid.
2: if we encounter 2, we will swap it with high, because high - 1 to N - 1 are 2s and we have to place all 2s together. By doing that, we will also decrease the value of high.
Code can be written as -
#include<iostream>
using namespace std;
int main() {
int arr[] = {0,1,0,2,0,0,1,2,2,1,2,1,0};
int low = 0, high = 12, mid = 0;
while(mid <= high) {
if (arr[mid] == 0) {
swap(arr[mid], arr[low]);
mid++;
low++;
} else if (arr[mid] == 1) {
mid++;
} else {
swap(arr[mid], arr[high]);
high--;
}
}
return 0;
}
Now, this is the most optimal way of sorting the array it only takes, O(N) time.
Hope you had learned something from this.
Thanks for scrolling!!
