K വലുപ്പമുള്ള എല്ലാ സബ്‌റേകളുടെയും ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ ഘടകങ്ങളുടെ ആകെത്തുക


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ബൈറ്റ്ഡാൻസ് ക്യാപിറ്റൽ വൺ കൂപ്പൺ‌ഡ്യൂണിയ ഡാറ്റാബ്രിക്സ് ഗൂഗിൾ ട്വിలియో യാൻഡക്സ്
അറേ വരി സ്ലൈഡിംഗ് വിൻഡോ

ഉള്ളടക്ക പട്ടിക

പ്രശ്നം പ്രസ്താവന

“വലുപ്പമുള്ള എല്ലാ സബ്‌റേകളുടെയും ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ മൂലകങ്ങളുടെ ആകെത്തുക” എന്ന പ്രശ്‌നം, നിങ്ങൾക്ക് പോസിറ്റീവ്, നെഗറ്റീവ് സംഖ്യകൾ അടങ്ങിയ ഒരു അറേ നൽകിയിട്ടുണ്ടെന്നും, കെ വലുപ്പത്തിന്റെ എല്ലാ ഉപ അറേകളിലെയും ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ ഘടകങ്ങളുടെ ആകെത്തുക കണ്ടെത്തുക.

ഉദാഹരണങ്ങൾ

arr[] = {5, 9, 8, 3, -4, 2, 1, -5}
k = 4
17

വിശദീകരണം
വലുപ്പം 4 ന്റെ എല്ലാ ഉപ അറേകളും,
{5, 9, 8, 3}: മിനിറ്റ് + പരമാവധി = 9 + 3 = 12
{9, 8, 3, -4}: മിനിറ്റ് + പരമാവധി = -4 + 9 = 5
{8, 3, -4, 2}: മിനിറ്റ് + പരമാവധി = -4 + 8 = 4
{3, -4, 2, 1}: മിനിറ്റ് + പരമാവധി = -4 + 3 = -1
{-4, 2, 1, -5}: മിനിറ്റ് + പരമാവധി = -5 + 2 = -3

K വലുപ്പമുള്ള എല്ലാ സബ്‌റേകളുടെയും ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ ഘടകങ്ങളുടെ ആകെത്തുക

arr[] = {1, -1, 2, -2, 3, -3}
k = 2
2

വിശദീകരണം
വലുപ്പം 2 ന്റെ എല്ലാ ഉപ അറേകളും,
{1, -1}: മിനിറ്റ് + പരമാവധി = -1 + 1 = 0
{-1, 2}: മിനിറ്റ് + പരമാവധി = -1 + 2 = 1
{2, -2}: മിനിറ്റ് + പരമാവധി = -2 + 2 = 0
{-2, 3}: മിനിറ്റ് + പരമാവധി = -2 + 3 = 1
{3, -3}: മിനിറ്റ് + പരമാവധി = -3 + 3 = 0

സമീപനം

നിഷ്കളങ്കമായ സമീപനം

വലുപ്പമുള്ള k ന്റെ എല്ലാ ഉപ അറേകളിലൂടെ സഞ്ചരിച്ച് അവയുടെ ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ ഘടകങ്ങൾ കണ്ടെത്തി തുക പ്രിന്റുചെയ്യുക.

  1. ഒരു വേരിയബിൾ തുക 0 ആയി സമാരംഭിക്കുക.
  2. I ന് 0 മുതൽ (n - k) വരെ തുല്യമായ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക, ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന മൂലകങ്ങളുടെ ആകെ എണ്ണമാണ് ശ്രേണി. ഓരോ i വലുപ്പവും k വലുപ്പമുള്ള ഒരു ഉപ-അറേയുടെ ആരംഭ പോയിന്റായി പ്രവർത്തിക്കുന്നു.
  3. J = i മുതൽ (i + k) വരെ ഒരു നെസ്റ്റഡ് ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക (ഉൾപ്പെടുത്തിയിട്ടില്ല), ഈ ലൂപ്പ് k വലുപ്പത്തിന്റെ ഉപ-അറേയെ പ്രതിനിധീകരിക്കുന്നു. ഈ ഉപ-അറേയിലൂടെ സഞ്ചരിച്ച് ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ ഘടകങ്ങൾ കണ്ടെത്തുക, ഇവ യഥാക്രമം മിനിറ്റും പരമാവധി ആയിരിക്കട്ടെ.
  4. തുകയിലേക്ക് (മിനിറ്റ് + പരമാവധി) ചേർക്കുക.
  5. ട്രാവെർസലിന്റെ അവസാനം, റിട്ടേൺ തുക.

ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന അറേയിലെ ആകെ ഘടകങ്ങളുടെ എണ്ണം.

K വലുപ്പമുള്ള എല്ലാ സബ്‌റേകളുടെയും ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ ഘടകങ്ങളുടെ ആകെത്തുക കണ്ടെത്താനുള്ള ജാവ കോഡ്

class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
    private static int sumOfMinMax(int[] arr, int k) {
        int n = arr.length;
        // initialize sum as 0
        int sum = 0;

        // Traverse all the subarray of size k one by one
        for (int i = 0; i <= n - k; i++) {
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            // traverse the current subarray and find the min and max
            for (int j = i; j < i + k; j++) {
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);
            }

            // add (min + max) to the sum
            sum += (min + max);
        }

        return sum;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
        int k1 = 4;
        System.out.println(sumOfMinMax(arr1, k1));

        // Example 2
        int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
        int k2 = 2;
        System.out.println(sumOfMinMax(arr2, k2));
    }
}
17
2

കെ വലുപ്പമുള്ള എല്ലാ സബ്‌റേകളുടെയും ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ ഘടകങ്ങളുടെ ആകെത്തുക കണ്ടെത്താനുള്ള സി ++ കോഡ്

#include<bits/stdc++.h> 
using namespace std; 

int sumOfMinMax(int *arr, int k, int n) {
    // initialize sum as 0
    int sum = 0;
    
    // Traverse all the subarray of size k one by one
    for (int i = 0; i <= (n - k); i++) {
        int min = INT_MAX;
        int max = INT_MIN;
        // traverse the current subarray and find the min and max
        for (int j = i; j < i + k; j++) {
            min = std::min(min, arr[j]);
            max = std::max(max, arr[j]);
        }
        
        // add (min + max) to the sum
        sum += (min + max);
    }
    
    return sum;
}

int main() {
    // Example 1
    int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
    int k1 = 4;
    cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, -1, 2, -2, 3, -3};
    int k2 = 2;
    cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
17
2

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത = O (n * k)
ബഹിരാകാശ സങ്കീർണ്ണത = O (1)

ഇവിടെ സമയ സങ്കീർണ്ണത പോളിനോമിയലാണ്, കാരണം ഓരോ ഉപ-അറേയുടെയും പ്രശ്നം ഞങ്ങൾ സ്വതന്ത്രമായി പരിഹരിക്കുന്നു. ഞങ്ങൾ സംഭരിക്കുന്നതിനാൽ; പരമാവധി, കുറഞ്ഞത് എന്നിവയ്ക്കുള്ള രണ്ട് വേരിയബിളുകൾ, ആവശ്യമായ ഇടം സ്ഥിരമാണ്.

ഒപ്റ്റിമൽ സമീപനം

രണ്ട് സൃഷ്ടിക്കുക ഡെക്ക് d1, d2, രണ്ട് ഡെക്കുകളും ഒരു ഉപ-അറേയുടെ ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ സംഭാവനകളുടെ ഘടകങ്ങളുടെ സൂചികകൾ സംഭരിക്കുന്നു. മുന്നിൽ നിന്ന് പിന്നിലേക്ക് ക്രമം കുറയ്ക്കുന്നതിനുള്ള ഘടകങ്ങൾ Deque d1 ൽ അടങ്ങിയിരിക്കുന്നു, മുന്നിൽ നിന്ന് പിന്നിലേക്ക് ക്രമം വർദ്ധിപ്പിക്കുന്ന ഘടകങ്ങൾ d2 ൽ അടങ്ങിയിരിക്കുന്നു.

  1. ഒരു വേരിയബിൾ തുക 0 ആയി സമാരംഭിക്കുക. D1, d2 എന്നീ രണ്ട് ഡീക്കുകൾ സൃഷ്ടിക്കുക. K വലുപ്പത്തിന്റെ ആദ്യ ഉപ-ശ്രേണി പരിഗണിക്കുക.
  2. വലിപ്പം k ന്റെ ഉപ-അറേയുടെ നിലവിലെ ഘടകം d1 ന്റെ സൂചിക പിൻ‌ഭാഗത്തുള്ള മൂലകത്തേക്കാൾ വലുതോ തുല്യമോ ആണെങ്കിലും, Deque d1 ന്റെ പിൻ‌ മൂലകം നീക്കംചെയ്യുക.
  3. വലിപ്പം k ന്റെ ഉപ-അറേയുടെ നിലവിലെ ഘടകം d2 ന്റെ സൂചിക പിൻ‌ഭാഗത്തുള്ള മൂലകത്തേക്കാൾ ചെറുതോ തുല്യമോ ആണെങ്കിലും, Deque d2 ന്റെ പിൻ‌ മൂലകം നീക്കംചെയ്യുക.
  4. രണ്ട് ഡെക്കുകളുടെയും പിന്നിലേക്ക് നിലവിലെ സൂചിക ചേർക്കുക.
  5. ഡെക്ക് ഡി 1 ന്റെ പിൻഭാഗം ഉപ-അറേയുടെ പരമാവധി മൂലകത്തിന്റെ സൂചികയാണ്, ഡെക്ക് ഡി 2 ന്റെ പിൻഭാഗം ഉപ-അറേയുടെ ഏറ്റവും കുറഞ്ഞ മൂലകത്തിന്റെ സൂചികയാണ്. വേരിയബിൾ തുകയിലേക്ക് പരമാവധി, കുറഞ്ഞ മൂലകത്തിന്റെ തുക ചേർക്കുക.
  6. K വലുപ്പത്തിന്റെ ശേഷിക്കുന്ന ഉപ അറേകളിലൂടെ സഞ്ചരിച്ച് 2 മുതൽ 5 വരെയുള്ള ഘട്ടങ്ങൾ ആവർത്തിക്കുക. ശേഷിക്കുന്ന എല്ലാ ഉപ-അറേകൾക്കും സ്ലൈഡിംഗ് വിൻഡോ ടെക്നിക് മുമ്പത്തെ ഉപ-അറേയിൽ ഇല്ലാത്ത ഘടകം മാത്രം പ്രോസസ്സ് ചെയ്യുക.
  7. എല്ലാ ഉപ അറേകളിലൂടെയും സഞ്ചരിച്ച ശേഷം, തുക തിരികെ നൽകുക.

കെ വലുപ്പമുള്ള എല്ലാ സബ്‌റേകളുടെയും ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ ഘടകങ്ങളുടെ ആകെത്തുക കണ്ടെത്താനുള്ള ജാവ കോഡ്

import java.util.Deque;
import java.util.LinkedList;

class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
    private static int sumOfMinMax(int[] arr, int k) {
        int n = arr.length;
        // initialize sum as 0
        int sum = 0;

        // create 2 deques d1 and d2
        Deque<Integer> d1 = new LinkedList<>();
        Deque<Integer> d2 = new LinkedList<>();

        // first subarray
        for (int i = 0; i < k; i++) {
            // only push the elements that may contribute to maximum
            while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
                d1.removeLast();

            // only push the elements that may contribute to minimum
            while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
                d2.removeLast();

            // add the current elememt's index
            d1.addLast(i);
            d2.addLast(i);
        }

        // sum of min and max for first subarray
        sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];

        // traverse the remaining subarray
        for (int i = k; i < n; i++) {
            // remove the previous element (sliding window technique)
            while (!d2.isEmpty() && d2.peekFirst() <= i - k)
                d2.removeFirst();
            while (!d1.isEmpty() && d1.peekFirst() <= i - k)
                d1.removeFirst();

            // only push the elements that may contribute to maximum
            while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
                d1.removeLast();

            // only push the elements that may contribute to minimum
            while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
                d2.removeLast();

            // add the current element's index
            d1.addLast(i);
            d2.addLast(i);

            // sum of min and max for current subarray
            sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];
        }

        // return total sum
        return sum;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
        int k1 = 4;
        System.out.println(sumOfMinMax(arr1, k1));

        // Example 2
        int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
        int k2 = 2;
        System.out.println(sumOfMinMax(arr2, k2));
    }
}
17
2

കെ വലുപ്പമുള്ള എല്ലാ സബ്‌റേകളുടെയും ഏറ്റവും കുറഞ്ഞതും കൂടിയതുമായ ഘടകങ്ങളുടെ ആകെത്തുക കണ്ടെത്താനുള്ള സി ++ കോഡ്

#include<bits/stdc++.h> 
using namespace std; 

int sumOfMinMax(int *arr, int k, int n) {
    // initialize sum as 0
    int sum = 0;
    
    // create 2 deques d1 and d2
    deque<int> d1;
    deque<int> d2;
    
    // first subarray
    for (int i = 0; i < k; i++) {
        // only push the elements that may contribute to maximum
        while (!d1.empty() && arr[d1.back()] <= arr[i]) {
            d1.pop_back();
        }
        
        // only push the elements that may contribute to minimum
        while (!d2.empty() && arr[d2.back()] >= arr[i]) {
            d2.pop_back();
        }
        
        // add the current element's index
        d1.push_back(i);
        d2.push_back(i);
    }
    
    // sum of min and max for first subarray
    sum += (arr[d2.front()] + arr[d1.front()]);
    
    // traverse the remaining subarray
    for (int i = k; i < n; i++) {
        // remove the previous element (sliding window technique)
        while (!d1.empty() && d1.front() <= (i -k)) {
            d1.pop_front();
        }
        while (!d2.empty() && d2.front() <= (i - k)) {
            d2.pop_front();
        }
        
        // only push the elements that may contribute to maximum
        while (!d1.empty() && arr[d1.back()] <= arr[i]) {
            d1.pop_back();
        }
        
        // only push the elements that may contribute to minimum
        while (!d2.empty() && arr[d2.back()] >= arr[i]) {
            d2.pop_back();
        }
        
        // add the current element's index
        d1.push_back(i);
        d2.push_back(i);
        
        // sum of min and max for current subarray
        sum += (arr[d1.front()] + arr[d2.front()]);
    }
    
    // return total sum
    return sum;
}

int main() {
    // Example 1
    int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
    int k1 = 4;
    cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, -1, 2, -2, 3, -3};
    int k2 = 2;
    cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
17
2

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത = O (n)
ബഹിരാകാശ സങ്കീർണ്ണത = O (n)
ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന അറേയിലെ ആകെ ഘടകങ്ങളുടെ എണ്ണം.

ക്രമം കുറയ്ക്കുന്നതിലും വർദ്ധിപ്പിക്കുന്നതിലും അക്കങ്ങളെ പ്രതിനിധീകരിക്കുന്ന ക്യൂകൾ ഞങ്ങൾ ഉപയോഗിച്ചിരിക്കുന്നതിനാൽ അവ ഘടകങ്ങൾ ഒരിക്കൽ സംഭരിക്കുന്നു. അങ്ങനെ അൽ‌ഗോരിതം രേഖീയ സമയം എടുക്കുന്നു, അതിനാൽ ആവശ്യമായ സ്ഥലവും രേഖീയമാണ്.