Find if Array Can Be Sorted | Detailed Approaches | Dry Runs | Leetcode 3011 | codestorywithMIK

This is the 120th Video of our Playlist "Array 1D/2D : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve a medium-easy Array based Problem which checks your fundamentals i.e. Bubble Sort : Find if Array Can Be Sorted | Detailed Approaches | Dry Runs | Leetcode 3011 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Find if Array Can Be Sorted | Detailed Approaches | Dry Runs | Leetcode 3011 | codestorywithMIK
Company Tags : will update

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Summary :
Bubble Sort with Swapping Condition Approach:

This method involves attempting to sort the array using a modified bubble sort algorithm.
During the sorting, adjacent elements are swapped only if they have the same number of set bits (1s in their binary representation).
If a swap is not allowed due to differing set bit counts and sorting becomes impossible, the function returns false.
The array is checked for complete sorting after each pass, and if no swaps are needed in a pass, the array is considered sorted and the function returns true.
Segmented Sorting by Set Bits Approach:

This approach involves dividing the array into segments based on the number of set bits in each element.
Each segment is treated independently, and elements within a segment are compared to find the segment's maximum and minimum.
A new segment starts when an element has a different number of set bits than the previous ones.
The algorithm checks if the minimum of the current segment is greater than or equal to the maximum of the previous segment to ensure correct ordering between segments.
If any segment fails this condition, the function returns false, indicating that sorting is not possible under the given constraints.
The function returns true if all segments are arranged properly by the end.

✨ Timelines✨
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[faizanmohammed]

Amazing, I learnt new thing about bubble sort that the largest element will be at correct place. Thank you so so so much.

[poorvajhinge]

most most easy explaination availabel on youtube thanks man

[Engineering.Wallah]

class Solution {
public:
bool canSortArray(vector<int>& nums) {
int i=0, n=nums.size();
int prevMax=INT_MIN, currMin=INT_MAX, currMax=INT_MIN;
while(i<n){
int
int
while(i<n && a==b){
currMin=min(currMin, nums[i]);
currMax=max(currMax, nums[i]);
i++;
if(i<n)

}
if(currMin<prevMax) return 0;
prevMax=currMax;
currMin=INT_MAX;
}
return 1;
}
};

[sksaffiulla]

I did get the intuition of the second approach but wasn't sure about it. Need to have some confidence.

[amanqureshi]

2nd Approach
class Solution {
public:
int setBits(int num){
int ans=0;
while(num>0){
if(num & 1) ans++;
num>>=1;
}
return ans;
}
bool canSortArray(vector<int>& nums) {
unordered_map<int, int> mp;
for(int num:nums){
int ans=setBits(num);
mp[num]=ans;
}
int r=0, l=0;
int maxPrev=-1;
int minCurr=-1;
int maxCurr=-1;
while(r<nums.size()){

if(minCurr==-1 && maxCurr==-1){
minCurr=nums[r];
maxCurr=nums[l];
}else{
minCurr=min(minCurr, nums[r]);
maxCurr=max(maxCurr, nums[r]);
}
}else{
if(maxPrev!=-1 && maxPrev>minCurr){
return false;
}
maxPrev=maxCurr;
minCurr=nums[r];
maxCurr=nums[r];
l=r;
}
r++;
}
if(maxPrev>minCurr) return false;
return true;
}
};

[learnergeek]

Source code of Approach one: (Time completexity O(n^2))

class Solution {
public:
bool canSortArray(vector<int>& nums) {
int n=nums.size();

bool swapped=true;

for (int i=0; i<n; i++){
swapped = false;

for(int j=0; j<n-i-1;j++){ //in every pass, the max element bubbles up to right most index.
if (nums[j] <= nums[j+1]) { //no swip required.
continue;
} else{ //sure nums[j]>nums[j+1]
//swap is required
==
swap(nums[j], nums[j+1]);
swapped=true;
} else {
//not ablt to swap, hence can't sort it.
return false;
}

}

}
if(swapped == false){ //no sewapped is done in the pass, hence array was already sorted.
break;
}
}
return true;
}
};

Aproach 2nd: (time complexity= O(n))
class Solution {
public:
bool canSortArray(vector<int>& nums) {
//Current Segment
int numOfSetBits = __builtin_popcount(nums[0]);
int maxOfSegment = nums[0];
int minOfSegment = nums[0];

int maxOfPrevSegment = INT_MIN;

for (int i = 1; i < nums.size(); i++) {
if (__builtin_popcount(nums[i]) == numOfSetBits) { //they belong to same segment
maxOfSegment = max(maxOfSegment, nums[i]); //find max of current segment
minOfSegment = min(minOfSegment, nums[i]); //find min of current segment
} else { // Element belongs to a new segment

if (minOfSegment < maxOfPrevSegment) { //ye bataya hai maine video me
return false;
}

// Update the previous segment's max
maxOfPrevSegment = maxOfSegment;

// new segment started now
maxOfSegment = nums[i];
minOfSegment = nums[i];
numOfSetBits = __builtin_popcount(nums[i]);
}
}
// Final check for proper segment arrangement
if (minOfSegment < maxOfPrevSegment) {
return false;
}
return true;
}
};

[gui-codes]

Awesome bhai. I was able to code 2nd Approach, it was too good.
Thanks a lot MIK.

[amitkumar-qnzo]

class Solution {
public:
bool canSortArray(vector<int>& nums) {
int n=nums.size();
int i=0, j=0;

vector<int> count(n, 0);

for(int i=0;i<n;i++){
int
count[i]=cnt;
}

int mx=INT_MIN;
while(j<n and count[i]==count[j]){
mx=max(mx, nums[j]);
j++;
}
i=j;

int prevMax=mx;

while(j<n){
int mn=INT_MAX;
mx=INT_MIN;
while(j<n and count[i]==count[j]){
mn=min(mn, nums[j]);
mx=max(mx, nums[j]);
j++;
}
if(prevMax>mn) return false;

i=j;
prevMax=mx;
}
return true;
}
};

[varunpalsingh]

bit manipulation ki bhi concept ki playlist bana do

[dayashankarlakhotia]

i have solved leetcode weekly contest qn no.2 and qn.no.3 watching your videos of dijkstra algorithms.

[aizadiqbal]

one doubt in the second approach, we do not need to group the numbers who have the same number of bits ?
that is what I was trying to do, and it was getting complex...even before your videos..
after watching your video then code then video again on the second part i got it finally

[VanshGupta]

class Solution {

private:
int countSetBits(int n) {
int count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}


public:
bool canSortArray(vector<int>& nums) {
//if it is not at its correct position and cant be swapped
bool ans = 1;
for(int i = 0; i < nums.size();i++){
for(int j = i + 1; j < nums.size();j++){
if(nums[i] > nums[j]){
if(countSetBits(nums[i]) != countSetBits(nums[j]) ){
ans = 0;
return ans;
}
}
}
}
return ans;
}
};

[kumarashutosh-pn]

@codestorywithmik OA ke liye content upload krdo

[madhumithaakula]

class Solution {
public:
int set_bits(int n){
int count=0;
while(n!=0){
count+=(n%2);//to know the count of set bits of a number
n=n/2;
}
return count;
}
bool canSortArray(vector<int>& nums) {
int n=nums.size();
for(int i=0;i<n;i++){
for(int j=0;j<n-1;j++){
int first=set_bits(nums[j]);
int second=set_bits(nums[j+1]);
if(first==second && nums[j]>nums[j+1]){
int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
return is_sorted(nums.begin(), nums.end());
}
};

[nitishgupta]

Hey Mik have a look at this code . this is my brute force approach.

class Solution {
public:
bool canSortArray(vector<int>& nums) {
vector<int>temp;
int n = nums.size();
for(int i =0;i<n;i++)
{
int cntofsetbit = __builtin_popcount(nums[i]);
temp.push_back(cntofsetbit);
}

for(int i = 0;i<n;i++)
{
for(int j = i+1;j<n;j++)
{
if(nums[i]>nums[j] && temp[i]!=temp[j])
{
return false;
}
}
}
return true;
}
};

[mdfarhan]

please make a playlist for bit manipulation

[jvinay]

Using sorting and mapping se bhi kar skte hein

[RishabhChatterjee-fggz]

Bhaiya can you please make video how to observe these from any problem, and how to build intuition

Please Bhaiya

[tushuoye]

I did the question using bubble sort then I came to watch your approach but it's the same
We all thinking the same damn matrix

[RajaChakraborty-ot]

/* 2nd Approach */
TC = O(n * 32) to fill the bits array + O(n) to do the rest of the ops
SC = O(n) for bits array

/* CODE */
class Solution {
public void f(int[] a, int[] bits){
for(int i = 0; i < a.length; i++){
int x = a[i];
int cnt = 0;

while(x != 0){
x &= (x - 1);
cnt++;
}

bits[i] = cnt;
}
}
public boolean canSortArray(int[] a) {
int n = a.length;
int currSetBits = -1;

int prevMax = -1;
int prevMin = -1;
int currMax = -1;
int currMin = -1;

int[] bits = new int[n];
f(a, bits);

for(int i = 0; i < n; i++){
if(currSetBits == -1){
currSetBits = bits[i];
currMax = a[i];
currMin = a[i];
}
else if(currSetBits != bits[i]){
if(prevMax > currMin) return false;
prevMax = currMax;
prevMin = currMin;
currMax = a[i];
currMin = a[i];
currSetBits = bits[i];
}
else if(currSetBits == bits[i]){
currMax = Math.max(currMax, a[i]);
currMin = Math.min(currMin, a[i]);
}
}

return prevMax < currMin;
}
}