ਨਿਰੰਤਰ ਐਰੇ ਲੀਟਕੋਡ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਫੇਸਬੁੱਕ ਗੂਗਲ
ਅਰੇ ਹੈਸ਼ਿੰਗ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

“ਕੰਨਟਿਜਿਵ ਐਰੇ ਲੀਟਕੋਡ” ਸਮੱਸਿਆ ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਇਕ ਐੱਨ ਐਰੇ a [] ਅਕਾਰ ਦੇ n ਵਿੱਚ ਸਿਰਫ 1 ਅਤੇ 0 ਦੇ ਹੁੰਦੇ ਹਨ. ਲੱਭੋ ਲੰਬੇ ਲੰਬੇ subarray ਜਿਸ ਵਿਚ 1 ਦੀ ਗਿਣਤੀ 0 ਦੀ ਗਿਣਤੀ ਦੇ ਬਰਾਬਰ ਹੈ.

ਉਦਾਹਰਨ

ਨਿਰੰਤਰ ਐਰੇ ਲੀਟਕੋਡ

a[ ] = {1, 0, 1, 1, 1, 0, 0}
1 to 6

ਵਿਆਖਿਆ: ਇੰਡੈਕਸ 1 ਤੋਂ 6 ਤੱਕ ਇਕ ਸਬਅਰੇਰੇ ਦੀ ਚੋਣ ਕਰਨਾ ਸਾਨੂੰ ਲੰਬਾਈ 6 ਦਾ ਸਭ ਤੋਂ ਵਧੀਆ ਨਤੀਜਾ ਦਿੰਦਾ ਹੈ. 1 ਤੋਂ 6 ਇੰਡੈਕਸ ਤੱਕ ਸੰਖੇਪ ਐਰੇ ਵਿਚ 3 ਜ਼ੀਰੋ ਅਤੇ 3 ਹਨ. ਇੱਥੇ ਅਸੀਂ 0 ਅਧਾਰਤ ਇੰਡੈਕਸਿੰਗ 'ਤੇ ਵਿਚਾਰ ਕੀਤਾ ਹੈ.

a[ ] = {1, 1}
No such subarray

ਪਹੁੰਚ

ਭੋਲਾ ਵਿਧੀ

ਹਰ ਸੰਭਵ ਉਪਨਗਰਸ ਤਿਆਰ ਕਰੋ. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਕੋਈ ਉਪਨਗਰ ਮੌਜੂਦ ਹੈ ਜਿਸ ਵਿੱਚ 1 ਦੀ ਗਿਣਤੀ 0 ਦੀ ਗਿਣਤੀ ਦੇ ਬਰਾਬਰ ਹੈ. ਅਸੀਂ ਇੱਕ ਸੂਬਰੇ ਦੀ ਖੱਬੀ ਅਤੇ ਸੱਜੀ ਸੀਮਾ ਲਈ ਦੋ ਪੁਆਇੰਟਰ i ਅਤੇ j ਵਰਤਦੇ ਹਾਂ. ਫਿਰ ਅਸੀਂ ਜਾਂਚ ਕਰਦੇ ਹਾਂ ਕਿ ਕੀ i ਤੋਂ j ਤੱਕ subarray ਦੇ ਜੋੜ ਦਾ ਜੋੜ = 0 ਹੈ, 0 ਨੂੰ -1 ਨਾਲ ਤਬਦੀਲ ਕਰਨ ਤੋਂ ਬਾਅਦ. ਜੇ ਇਹ ਸੱਚ ਹੈ, ਤਾਂ ਸਾਨੂੰ ਹਾਲਤਾਂ ਨੂੰ ਸੰਤੁਸ਼ਟ ਕਰਨ ਵਾਲਾ ਇੱਕ ਸਵੈਰਰੇ ਮਿਲਿਆ ਹੈ. ਹੁਣ ਅਸੀਂ ਆਪਣੇ ਜਵਾਬ ਨੂੰ ਅਪਡੇਟ ਕਰਦੇ ਹਾਂ.

ਨਿਰੰਤਰ ਐਰੇ ਲੀਟਕੋਡ ਸਮੱਸਿਆ ਲਈ ਐਲਗੋਰਿਦਮ

1. Initialize a binary array a[] of size n and three variables sum, max=-1, and start.
2. Traverse through the array and update sum as -1 if a[i] is 0 else 1.
3. Traverse the inner loop and add -1 in sum if a[i] is 0 else 1.
4. Check if the sum is 0 and max is less than j-i+1, update max as j-i+1 and start as i.
5. Outside the loops check if max is -1 print "No such subarray" else print starting and ending index.

ਕੋਡ

C ++ ਪ੍ਰੋਗਰਾਮ ਕੰਨਟਿਗਿ .ਜ਼ ਐਰੇ ਲੀਟਕੋਡ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    int sum = 0; 
    int max = -1, start; 
  
    for(int i=0; i<n-1; i++){ 
        sum = (a[i]==0) ? -1 : 1; 
  
        for(int j=i+1; j<n; j++){ 
            (a[j]==0) ? (sum+=-1) : (sum+=1); 
  
            if(sum == 0 && max < j-i+1){ 
                max = j-i+1; 
                start = i; 
            } 
        } 
    } 
    if(max == -1) 
        cout<<"No such subarray"; 
    else
        cout<<start<<" to "<<start+max-1; 
  
    return max; 
} 
  
int main(){ 
    int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
}
1 to 6
ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ ਕੰਨਟਿਗ੍ਰੈਸ ਐਰੇ ਲੀਟਕੋਡ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ
class LongestSubArray{
    int subArray(int a[], int n){ 
        int sum = 0; 
        int max = -1, start=0,end=0; 
        
        for(int i=0; i<n-1; i++){ 
            sum = (a[i]==0) ? -1 : 1; 
            
            for(int j=i+1; j<n; j++){ 
                if(a[j] == 0) 
                    sum += -1; 
                else
                    sum += 1;  
                
                if(sum == 0 && max < j-i+1){ 
                    max = j-i+1; 
                    start = i; 
                } 
            } 
        } 
        if(max == -1) 
            System.out.println("No such subarray");
        else
            end = start+max-1;
            System.out.println(start+" to "+end);
        
        return max; 
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਕਿਉਂਕਿ ਇੱਥੇ ਅਸੀਂ ਇਕ ਪੁਆਇੰਟਰ ਨੂੰ ਸਥਿਰ ਰੱਖਦੇ ਹੋਏ ਐਰੇ ਨੂੰ ਟ੍ਰਾੱਰ ਕਰ ਰਹੇ ਸੀ. ਦੀ ਬਹੁਪੱਖੀ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਪ੍ਰਾਪਤ ਕੀਤਾ  ਓ (ਐਨ2) ਜਿੱਥੇ n ਦਿੱਤੀ ਗਈ ਐਰੇ ਵਿੱਚ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਏ [] ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1) ਕਿਉਂਕਿ ਅਸੀਂ ਨਿਰੰਤਰ ਵਧੇਰੇ ਜਗ੍ਹਾ ਦੀ ਵਰਤੋਂ ਕੀਤੀ. ਅਸੀਂ ਸਿਰਫ ਪਰਿਵਰਤਨ ਦੀ ਨਿਰੰਤਰ ਗਿਣਤੀ ਬਣਾਈ ਹੈ. ਪਰ ਸ਼ੁਰੂਆਤੀ ਇਨਪੁਟ ਐਰੇ ਤੋਂ ਇਲਾਵਾ ਕਿਸੇ ਵੀ ਐਰੇ ਦੀ ਵਰਤੋਂ ਨਹੀਂ ਕੀਤੀ. ਪਰ ਪੂਰੇ ਪ੍ਰੋਗਰਾਮ ਵਿਚ ਓ (ਐਨ) ਸਪੇਸ ਗੁੰਝਲਦਾਰਤਾ ਹੈ ਕਿਉਂਕਿ ਅਸੀਂ ਇਨਪੁਟ ਐਲੀਮੈਂਟਸ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਐਰੇ ਦੀ ਵਰਤੋਂ ਕੀਤੀ.

ਹੈਸ਼ ਨਕਸ਼ੇ ਦੀ ਵਰਤੋਂ ਕਰਨਾ

ਨਿਰੰਤਰ ਐਰੇ ਲੀਟਕੋਡ ਸਮੱਸਿਆ ਲਈ ਐਲਗੋਰਿਦਮ

1. Initialize a binary array a[] of size n.
2. Initialize an unordered map.
3. Traverse through the array and update the array value of the current index as -1 if current value if 0 else 1.
4. Traverse through the array and add the elements.
5. If the sum is 0, update max as i+1 and end as i.
6. Else Traverse map and update max as i - map(sum+n) and end as i if max is less than i - map(sum+n) else update map(sum+n) as i.
7. Traverse through the array and update the array value of the current index as 0 if current value is -1 else 1.
8. If the end is greater than -1 print starting and ending index.
9. Else print "No such subarray".

ਅਸੀਂ ਇੱਥੇ ਕੀ ਕੀਤਾ ਹੈ, ਬਸ ਜਦੋਂ ਵੀ ਸਾਨੂੰ ਸਭ ਤੋਂ ਵੱਡੇ ਸਬਅਰਰੇ ਨੂੰ ਜੋੜਨ ਦੀ ਜ਼ਰੂਰਤ ਹੁੰਦੀ ਹੈ. 0. ਅਸੀਂ ਕੀ ਕਰਦੇ ਹਾਂ ਅਸੀਂ ਅਗੇਤਰ ਦੀ ਰਕਮ ਲੈਂਦੇ ਹਾਂ ਅਤੇ ਆਪਣੇ ਨਕਸ਼ੇ 'ਤੇ ਚੈੱਕ-ਇਨ ਕਰਦੇ ਹਾਂ ਜੇ ਕੋਈ ਜਗ੍ਹਾ ਹੈ ਜਿਥੇ ਸਾਨੂੰ ਉਹੀ ਰਕਮ ਮਿਲ ਸਕਦੀ ਹੈ. ਫਿਰ ਮੌਜੂਦਾ ਇੰਡੈਕਸ ਤੋਂ ਨਕਸ਼ੇ +1 ਵਿਚ ਸਟੋਰ ਕੀਤੀ ਕੀਮਤ ਤੋਂ ਸ਼ੁਰੂ ਹੋਣ ਵਾਲੇ ਸਬਅਰੇਅ ਦਾ ਜੋੜ 0. ਹੈ. ਇੱਥੇ, ਅਸੀਂ (ਜੋੜ + ਐਨ) ਨੂੰ ਕੁੰਜੀ ਦੇ ਤੌਰ ਤੇ ਵਰਤ ਰਹੇ ਹਾਂ. ਪਰ ਅਸੀਂ ਸਿੱਧੇ ਤੌਰ 'ਤੇ ਰਕਮ ਦੀ ਵਰਤੋਂ ਵੀ ਕਰ ਸਕਦੇ ਹਾਂ. ਪਰ ਜੇ ਅਸੀਂ (ਜੋੜ + ਐਨ) ਨੂੰ ਇੱਕ ਕੁੰਜੀ ਦੇ ਤੌਰ ਤੇ ਵਰਤਦੇ ਹਾਂ ਤਾਂ ਅਸੀਂ ਹੈਸ਼ਮੈਪ ਦੀ ਬਜਾਏ ਐਰੇ ਵੀ ਵਰਤ ਸਕਦੇ ਹਾਂ. ਕਿਉਂਕਿ ਫਿਰ ਅਸੀਂ ਯਕੀਨ ਕਰ ਸਕਦੇ ਹਾਂ ਕਿ (ਜੋੜ + n)> = 0 ਅਤੇ ਐਰੇ ਇੰਡੈਕਸਿੰਗ 0 ਤੋਂ ਸ਼ੁਰੂ ਹੁੰਦੀ ਹੈ.

ਕੋਡ

C ++ ਪ੍ਰੋਗਰਾਮ ਕੰਨਟਿਗਿ .ਜ਼ ਐਰੇ ਲੀਟਕੋਡ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    
    unordered_map<int, int> hM; 
  
    int sum = 0, max = 0, end = -1; 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == 0) ? -1 : 1; 
  
    for(int i=0; i<n; i++){ 
        sum += a[i]; 
  
        if(sum == 0){ 
            max = i + 1; 
            end = i; 
        } 
  
        if(hM.find(sum + n) != hM.end()){ 
            if(max < i - hM[sum + n]){ 
                max = i - hM[sum + n]; 
                end = i; 
            } 
        } 
        else 
            hM[sum + n] = i; 
    } 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == -1) ? 0 : 1; 
        
    if(end>-1)
        cout<<end - max + 1<<" to "<<end; 
    else
        cout<<"No such subarray";
    return max; 
} 
  
int main(){ 
    int a[] = {1, 0, 1, 1, 1, 0, 0}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
} 
1 to 6
ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ ਕੰਨਟਿਗ੍ਰੈਸ ਐਰੇ ਲੀਟਕੋਡ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ
import java.util.HashMap;

class LongestSubArray{
    int subArray(int a[], int n){ 
        
        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); 
  
        int sum = 0, max = 0, end = -1, start = 0; 
  
        for(int i=0; i<n; i++){ 
            a[i]=(a[i]==0) ? -1 : 1; 
        } 
  
        for(int i=0; i<n; i++){ 
            sum += a[i]; 
  
            if(sum == 0){ 
                max = i + 1; 
                end = i; 
            } 
  
            if(hM.containsKey(sum + n)){ 
                if(max < i - hM.get(sum + n)){ 
                    max = i - hM.get(sum + n); 
                    end = i; 
                } 
            } 
            else 
                hM.put(sum + n, i); 
        } 
  
        for(int i=0; i<n; i++) { 
            a[i] = (a[i] == -1) ? 0 : 1; 
        } 
  
        int index = end - max + 1; 
        
        if(end>-1)
            System.out.println(index + " to " + end); 
        else
            System.out.println("No such subarray"); 
        return max;  
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਜਿੱਥੇ n ਦਿੱਤੀ ਗਈ ਐਰੇ ਵਿੱਚ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਏ [] ਹੈ. ਕਿਉਂਕਿ ਈ ਨੇ ਅਣ-ਨਿਯਮਤ_ਮੈਪ / ਹੈਸ਼ਮੈਪ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਹੈ, ਅਸੀਂ ਓ (ਐਨ) ਟਾਈਮ ਪ੍ਰਾਪਤ ਕਰਨ ਦੇ ਯੋਗ ਸੀ ਕਿਉਂਕਿ ਹੈਸ਼ਮੈਪ ਓ (1) ਨੂੰ ਇਨਸਰਟ ਖੋਜ, ਮਿਟਾਉਣ ਲਈ ਸਮਾਂ ਦਿੰਦਾ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਕਿਉਂਕਿ ਅਸੀਂ N ਵਾਧੂ ਥਾਂ ਦੀ ਵਰਤੋਂ ਕੀਤੀ. ਕਿਉਂਕਿ ਅਸੀਂ ਹੈਸ਼ਮੈਪ ਵਿਗਿਆਪਨ ਦੀ ਵਰਤੋਂ ਨਾਲ ਐਨ ਦੇ ਤੱਤ ਬਾਰੇ ਜਾਣਕਾਰੀ ਨੂੰ ਸਟੋਰ ਕੀਤਾ ਹੈ, ਸਭ ਤੋਂ ਭੈੜੇ ਹਾਲਾਤਾਂ ਵਿੱਚ ਜਿਸ ਵਿੱਚ ਐਨ ਤੱਤ ਹੋ ਸਕਦੇ ਹਨ.