Horje
For each value in [1, N] find Minimum element present in all Subarray of that size

Given an array A[] of size N, the task is to find the minimum element present in all subarrays for all sizes from 1 to N where all the elements in the array are in range 1 to N

Examples:

Input: A[ ] = {1, 2, 3}
Output: [-1, 2, 1]
Explanation: All subarrays of size 1 {{1}, {2}, {3}} there is no common value 
For subarrays of size 2 {{1, 2}, {2, 3}} the minimum common element is 2 
For subarrays of size 3 {{1, 2, 3}} the minimum common element is 1 Hence, ans=[-1, 2, 1]

Input: A[ ] = {1, 2, 1, 3, 1}
Output: [-1, 1, 1, 1, 1]

 

Naive Approach: The basic idea to solve the problem is to find all the subarrays for all the sizes in the range [1, N]. Now for all subarrays of the same size find the minimum common element in those subarrays. Follow the steps mentioned below to solve the problem:

  • Iterate a loop from i = 1 to N:
    • Create every possible subarray of size i.
    • Count the frequency of each element in all the subarrays.
    • Check if the occurrence of any element is equal to the total number of subarrays of that size
    • Store the first element satisfying  the above conditions
  • Return the resultant array of the minimum common elements.

Below is the implementation of the above approach.

C++

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// the minimum element array
// from size 1 to N
vector<int> Calculate_Min_array(vector<int>& A,
                                int N)
{
    // Minimum element array(ans)
    // Count array for every subsegment(cnt)
    // Total occurrence array in all
    // subsegment of a given size(res)
    vector<int> ans(N + 1, -1), cnt(N + 1, 0),
        res(N + 1, 0);
    for (int i = 1; i <= N; i++) {
 
        // Counting all the elements
        // for every subsegment of size i
        for (int j = 0; j < N - i + 1;
             j++) {
            for (int k = j; k < j + i;
                 k++) {
                cnt[A[k]]++;
            }
 
            // If count of element is
            // greater than 0 then
            // increment its occurrence
            for (int k = 1; k <= N; k++) {
                if (cnt[k]) {
 
                    // If element is present
                    // increase its count
                    res[k]++;
                    cnt[k] = 0;
                }
            }
        }
 
        // When occurrence of an element
        // is equal to total subsegment
        // of size i then we will get the
        // desired val for that subsegment
        for (int j = 1; j <= N; j++) {
            if (res[j] == (N - i + 1)) {
                ans[i] = j;
                break;
            }
            res[j] = 0;
        }
    }
 
    // Final array
    return ans;
}
 
// Print Function
void print(vector<int> vec, int N)
{
    vector<int> ans
        = Calculate_Min_array(vec, N);
 
    // Output
    for (int i = 1; i <= N; i++)
        cout << ans[i] << " ";
    cout << "\n";
}
 
// Driver code
int main()
{
    // Initialization of array
    vector<int> A = { 1, 2, 3 };
    int N = 3;
 
    // Calling function
    print(A, N);
    return 0;
}

Java

// Java code for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  // Function to calculate
  // the minimum element array
  // from size 1 to N
  public static int[] Calculate_Min_array(int A[], int N)
  {
    // Minimum element array(ans)
    // Count array for every subsegment(cnt)
    // Total occurrence array in all
    // subsegment of a given size(res)
    int ans[] = new int[N + 1];
    int cnt[] = new int[N + 1];
    int res[] = new int[N + 1];
 
    for (int i = 0; i < N + 1; i++) {
      ans[i] = -1;
    }
    for (int i = 1; i <= N; i++) {
 
      // Counting all the elements
      // for every subsegment of size i
      for (int j = 0; j < N - i + 1; j++) {
        for (int k = j; k < j + i; k++) {
          cnt[A[k]]++;
        }
 
        // If count of element is
        // greater than 0 then
        // increment its occurrence
        for (int k = 1; k <= N; k++) {
          if (cnt[k] != 0) {
 
            // If element is present
            // increase its count
            res[k]++;
            cnt[k] = 0;
          }
        }
      }
 
      // When occurrence of an element
      // is equal to total subsegment
      // of size i then we will get the
      // desired val for that subsegment
      for (int j = 1; j <= N; j++) {
        if (res[j] == (N - i + 1)) {
          ans[i] = j;
          break;
        }
        res[j] = 0;
      }
    }
 
    // Final array
    return ans;
  }
 
  // Print Function
  public static void print(int vec[], int N)
  {
    int ans[] = Calculate_Min_array(vec, N);
 
    // Output
    for (int i = 1; i <= N; i++)
      System.out.print(ans[i] + " ");
    System.out.println();
  }
  public static void main(String[] args)
  {
    int A[] = { 1, 2, 3 };
    int N = 3;
 
    // Calling function
    print(A, N);
  }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python code for the above approach
 
# Function to calculate
# the minimum element array
# from size 1 to N
def Calculate_Min_array(A, N):
   
    # Minimum element array(ans)
    # Count array for every subsegment(cnt)
    # Total occurrence array in all
    # subsegment of a given size(res)
    ans = [-1 for i in range(N + 1)]
    cnt = [0 for i in range(N + 1)]
    res = [0 for i in range(N + 1)]
    for i in range(1, N + 1):
 
        # Counting all the elements
        # for every subsegment of size i
        for j in range(N - i + 1):
            for k in range(j, j + i):
                cnt[A[k]] = cnt[A[k]] + 1
 
            # If count of element is
            # greater than 0 then
            # increment its occurrence
            for k in range(1, N + 1):
                if (cnt[k]):
 
                    # If element is present
                    # increase its count
                    res[k] += 1
                    cnt[k] = 0
 
        # When occurrence of an element
        # is equal to total subsegment
        # of size i then we will get the
        # desired val for that subsegment
        for j in range(1,N+1):
            if (res[j] == (N - i + 1)):
                ans[i] = j
                break
            res[j] = 0
 
    # Final array
    return ans
 
# Print Function
def Print(vec,N):
 
    ans = Calculate_Min_array(vec, N)
 
    # Output
    for i in range(1,N+1):
        print(ans[i] ,end = " ")
    print("")
 
# Driver code
 
# Initialization of array
A = [ 1, 2, 3 ]
N = 3
 
# Calling function
Print(A, N)
 
# This code is contributed by shinjanpatra

C#

// C# code for the above approach
using System;
class GFG {
 
    // Function to calculate
    // the minimum element array
    // from size 1 to N
    static int[] Calculate_Min_array(int[] A, int N)
    {
        // Minimum element array(ans)
        // Count array for every subsegment(cnt)
        // Total occurrence array in all
        // subsegment of a given size(res)
        int[] ans = new int[N + 1];
        int[] cnt = new int[N + 1];
        int[] res = new int[N + 1];
 
        for (int i = 0; i < N + 1; i++) {
            ans[i] = -1;
        }
        for (int i = 1; i <= N; i++) {
 
            // Counting all the elements
            // for every subsegment of size i
            for (int j = 0; j < N - i + 1; j++) {
                for (int k = j; k < j + i; k++) {
                    cnt[A[k]]++;
                }
 
                // If count of element is
                // greater than 0 then
                // increment its occurrence
                for (int k = 1; k <= N; k++) {
                    if (cnt[k] != 0) {
 
                        // If element is present
                        // increase its count
                        res[k]++;
                        cnt[k] = 0;
                    }
                }
            }
 
            // When occurrence of an element
            // is equal to total subsegment
            // of size i then we will get the
            // desired val for that subsegment
            for (int j = 1; j <= N; j++) {
                if (res[j] == (N - i + 1)) {
                    ans[i] = j;
                    break;
                }
                res[j] = 0;
            }
        }
 
        // Final array
        return ans;
    }
 
    // Print Function
    static void print(int[] vec, int N)
    {
        int[] ans = Calculate_Min_array(vec, N);
 
        // Output
        for (int i = 1; i <= N; i++)
            Console.Write(ans[i] + " ");
        Console.WriteLine();
    }
    public static int Main()
    {
        int[] A = new int[] { 1, 2, 3 };
        int N = 3;
 
        // Calling function
        print(A, N);
        return 0;
    }
}
 
// This code is contributed by Taranpreet

Javascript

<script>
    // JavaScript code for the above approach
 
    // Function to calculate
    // the minimum element array
    // from size 1 to N
    const Calculate_Min_array = (A, N) => {
     
        // Minimum element array(ans)
        // Count array for every subsegment(cnt)
        // Total occurrence array in all
        // subsegment of a given size(res)
        let ans = new Array(N + 1).fill(-1), cnt = new Array(N + 1).fill(0),
            res = new Array(N + 1).fill(0);
        for (let i = 1; i <= N; i++) {
 
            // Counting all the elements
            // for every subsegment of size i
            for (let j = 0; j < N - i + 1;
                j++) {
                for (let k = j; k < j + i;
                    k++) {
                    cnt[A[k]]++;
                }
 
                // If count of element is
                // greater than 0 then
                // increment its occurrence
                for (let k = 1; k <= N; k++) {
                    if (cnt[k]) {
 
                        // If element is present
                        // increase its count
                        res[k]++;
                        cnt[k] = 0;
                    }
                }
            }
 
            // When occurrence of an element
            // is equal to total subsegment
            // of size i then we will get the
            // desired val for that subsegment
            for (let j = 1; j <= N; j++) {
                if (res[j] == (N - i + 1)) {
                    ans[i] = j;
                    break;
                }
                res[j] = 0;
            }
        }
 
        // Final array
        return ans;
    }
 
    // Print Function
    const print = (vec, N) => {
        let ans
            = Calculate_Min_array(vec, N);
 
        // Output
        for (let i = 1; i <= N; i++)
            document.write(`${ans[i]} `);
        document.write("<br/>");
    }
 
    // Driver code
 
    // Initialization of array
    let A = [1, 2, 3];
    let N = 3;
 
    // Calling function
    print(A, N);
 
// This code is contributed by rakeshsahni
 
</script>

Output

-1 2 1

Time Complexity: O(N3)
Auxiliary Space: O(N)

Efficient Approach: The idea to solve the problem efficiently is as follows:

If two consecutive occurrence of a value A[i] is maximum x, then it is part of all the subarrays of size x but not of all subarrays with size less than x. 

Follow the steps below to implement the above idea:

  • Create an array (say pos[i]) for each ith element to store the positions of the ith element the array.
  • Then calculate the value of the maximum adjacent difference for every element.
  • Iterate from i = 1 to N:
    • Start another loop from j = maximum adjacent difference two i to N:
      • If the answer for jth size subarray is not found then i is the minimum common element for all j sized subarray and continue for higher values of j.
      • Otherwise, break from the loop because all the higher values must also be filled
  • Return the resultant array.

Below is the implementation of the above approach:

C++

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// the minimum element array
// from size 1 to N
vector<int> Calculate_Min_array(vector<int>& A,
                                int N)
{
 
    vector<int> mx(N + 1, -1), ans(N + 1, -1);
    vector<int> pos[N + 1];
 
    // Inserting the first position
    // of elements
    for (int i = 1; i <= N; i++) {
        pos[i].push_back(0);
    }
 
    // Inserting the diff position
    // of elements
    for (int i = 0; i < N; i++) {
        int x = A[i];
        pos[x].push_back(i + 1);
    }
 
    // Inserting the last position
    // of elements
    for (int i = 1; i <= N; i++) {
        pos[i].push_back(N + 1);
    }
 
    // Calculating max adjacent diff
    // of elements
    for (int i = 1; i <= N; i++) {
        for (int j = 0;
             j < pos[i].size() - 1; j++) {
            mx[i] = max(mx[i],
                        pos[i][j + 1]
                            - pos[i][j]);
        }
    }
 
    // Calculating ans for every subarray size
    for (int i = 1; i <= N; i++) {
        for (int j = mx[i]; j <= N; j++) {
 
            // If ans[j] is already present
            // move to next element
            if (ans[j] != -1)
                break;
 
            // Otherwise store the ans[j]=i
            ans[j] = i;
        }
    }
 
    // Final array
    return ans;
}
 
// Print Function
void print(vector<int> A, int N)
{
    // Calculation Minimum element array
    // For Every subsegment length from
    // 1 to N
    vector<int> ans
        = Calculate_Min_array(A, N);
 
    // Output
    for (int i = 1; i <= N; i++)
        cout << ans[i] << " ";
    cout << "\n";
}
 
// Driver code
int main()
{
    int N = 3;
 
    // Initialization of array
    vector<int> A = { 1, 2, 3 };
    print(A, N);
    return 0;
}

Java

// Java code for the above approach:
import java.util.*;
class GFG
{
 
  // Function to calculate
  // the minimum element array
  // from size 1 to N
  static int[] Calculate_Min_array(int[] A, int N)
  {
    int mx[] = new int[N + 1];
    int ans[] = new int[N + 1];
    int[][] pos = new int[N + 1][N + 1];
 
    for (int i = 0; i <= N; i++) {
      mx[i] = -1;
      ans[i] = -1;
    }
 
    HashMap<Integer, Integer> map = new HashMap<>();
 
    // Inserting the first position
    // of elements
    for (int i = 1; i <= N; i++) {
      pos[i][0] = 0;
      map.put(i, 1);
    }
 
    // Inserting the diff position
    // of elements
    for (int i = 0; i < N; i++) {
      int x = A[i];
      int ind = map.get(x);
      pos[x][ind] = i + 1;
      map.put(x, ++ind);
    }
 
    // Inserting the last position
    // of elements
    for (int i = 1; i <= N; i++) {
      int ind = map.get(i);
      pos[i][ind] = N + 1;
      map.put(i, ++ind);
    }
 
    // Calculating max adjacent diff
    // of elements
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j < map.get(i) - 1; j++) {
        mx[i]  = Math.max(mx[i], pos[i][j + 1]
                          - pos[i][j]);
      }
    }
 
    // Calculating ans for every subarray size
    for (int i = 1; i <= N; i++) {
      for (int j = mx[i]; j <= N; j++) {
 
        // If ans[j] is already present
        // move to next element
        if (ans[j] != -1)
          break;
 
        // Otherwise store the ans[j]=i
        ans[j] = i;
      }
    }
 
    // Final array
    return ans;
  }
 
  // Print Function
  static void print(int[] A, int N)
  {
 
    // Calculation Minimum element array
    // For Every subsegment length from
    // 1 to N
    int[] ans = Calculate_Min_array(A, N);
 
    // Output
    for (int i = 1; i <= N; i++)
      System.out.print(ans[i] + " ");
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Initialization of array
    int N = 3;
    int A[] = { 1, 2, 3 };
 
    // Driver code
    print(A, N);
  }
}
 
// This code is contributed by phasing17

Python3

# Python code for the above approach:
 
# Function to calculate
# the minimum element array
# from size 1 to N
def Calculate_Min_array(A, N):
    mx, ans, pos = [-1 for i in range(N + 1)] , [-1 for i in range(N + 1)] , [[] for i in range(N + 1)]
     
    # Inserting the first position
    # of elements
    for i in range(1, N + 1):
        pos[i].append(0)
 
    # Inserting the diff position
    # of elements
    for i in range(N):
        x = A[i]
        pos[x].append(i + 1)
 
    # Inserting the last position
    # of elements
    for i in range(1, N + 1):
        pos[i].append(N + 1)
 
    # Calculating max adjacent diff
    # of elements
    for i in range(1, N + 1):
        for j in range(len(pos[i]) - 1):
            mx[i] = max(mx[i], pos[i][j + 1] - pos[i][j])
 
    # Calculating ans for every subarray size
    for i in range(1, N + 1):
        for j in range(mx[i], N + 1):
 
            # If ans[j] is already present
            # move to next element
            if (ans[j] != -1):
                break
 
            # Otherwise store the ans[j]=i
            ans[j] = i
 
    # Final array
    return ans
 
# Print Function
def Print(A, N):
 
    # Calculation Minimum element array
    # For Every subsegment length from
    # 1 to N
    ans = Calculate_Min_array(A, N)
 
    # Output
    for i in range(1, N + 1):
        print(ans[i], end = " ")
    print("")
 
# Driver code
N = 3
 
# Initialization of array
A = [ 1, 2, 3 ]
Print(A, N)
 
# This code is contributed by shinjanpatra

C#

// C# code for the above approach:
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to calculate
  // the minimum element array
  // from size 1 to N
  static int[] Calculate_Min_array(int[] A, int N)
  {
    int []mx = new int[N + 1];
    int []ans = new int[N + 1];
    int[,] pos = new int[N + 1,N + 1];
 
    for (int i = 0; i <= N; i++) {
      mx[i] = -1;
      ans[i] = -1;
    }
 
    Dictionary<int, int> map = new Dictionary<int, int>();
 
    // Inserting the first position
    // of elements
    for (int i = 1; i <= N; i++) {
      pos[i,0] = 0;
      map.Add(i, 1);
    }
 
    // Inserting the diff position
    // of elements
    for (int i = 0; i < N; i++) {
      int x = A[i];
      int ind = map[x];
      pos[x,ind] = i + 1;
      map[x] =  map[x] + ind++;
    }
 
    // Inserting the last position
    // of elements
    for (int i = 1; i <= N; i++) {
      int ind = map[i];
      pos[i,ind] = N + 1;
      map[i] =  map[i] + ind++;
 
    }
 
    // Calculating max adjacent diff
    // of elements
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j < map[i] - 1; j++) {
        mx[i]  = Math.Max(mx[i], pos[i,j + 1]
                          - pos[i,j]);
      }
    }
 
    // Calculating ans for every subarray size
    for (int i = 1; i <= N; i++) {
      for (int j = mx[i]; j <= N; j++) {
 
        // If ans[j] is already present
        // move to next element
        if (ans[j] != -1)
          break;
 
        // Otherwise store the ans[j]=i
        ans[j] = i;
      }
    }
 
    // Final array
    return ans;
  }
 
  // Print Function
  static void print(int[] A, int N)
  {
 
    // Calculation Minimum element array
    // For Every subsegment length from
    // 1 to N
    int[] ans = Calculate_Min_array(A, N);
 
    // Output
    for (int i = 1; i <= N; i++)
      Console.Write(ans[i] + " ");
  }
 
  // Driver code
  public static void Main(String[] args)
  {
 
    // Initialization of array
    int N = 3;
    int []A = { 1, 2, 3 };
 
    // Driver code
    print(A, N);
  }
}
 
 
// This code contributed by shikhasingrajput

Javascript

<script>
 
// JavaScript code for the above approach:
 
// Function to calculate
// the minimum element array
// from size 1 to N
function Calculate_Min_array(A,N)
{
 
    let mx = new Array(N + 1).fill(-1);
    let ans = new Array(N + 1).fill(-1);
    let pos = new Array(N + 1);
    for(let i=0;i<N + 1;i++){
        pos[i] = new Array();
    }
 
    // Inserting the first position
    // of elements
    for (let i = 1; i <= N; i++) {
 
        pos[i].push(0);
    }
 
    // Inserting the diff position
    // of elements
    for (let i = 0; i < N; i++) {
        let x = A[i];
        pos[x].push(i + 1);
    }
 
    // Inserting the last position
    // of elements
    for (let i = 1; i <= N; i++) {
        pos[i].push(N + 1);
    }
 
    // Calculating max adjacent diff
    // of elements
    for (let i = 1; i <= N; i++) {
        for (let j = 0;
            j < pos[i].length - 1; j++) {
            mx[i] = Math.max(mx[i],
                        pos[i][j + 1]
                            - pos[i][j]);
        }
    }
 
    // Calculating ans for every subarray size
    for (let i = 1; i <= N; i++) {
        for (let j = mx[i]; j <= N; j++) {
 
            // If ans[j] is already present
            // move to next element
            if (ans[j] != -1)
                break;
 
            // Otherwise store the ans[j]=i
            ans[j] = i;
        }
    }
 
    // Final array
    return ans;
}
 
// Print Function
function print(A,N)
{
    // Calculation Minimum element array
    // For Every subsegment length from
    // 1 to N
    let ans = Calculate_Min_array(A, N);
 
    // Output
    for (let i = 1; i <= N; i++){
        document.write(ans[i]," ");
    }
    document.write("</br>");
}
 
// Driver code
let N = 3;
 
// Initialization of array
let A = [ 1, 2, 3 ];
print(A, N)
 
// This code is contributed by shinjanpatra
 
</script>

Output

-1 2 1

Time complexity: O(N) Because though nested loops are used but at most N points are filled and one point is visited at most twice
Auxiliary Space: O(N) Though array of vectors is used but total points stored is N


 


Reffered: https://www.geeksforgeeks.org

Analysis Of Algorithms

Related
RFM Analysis Analysis Using Python RFM Analysis Analysis Using Python
Miscellaneous Problems of Time Complexity Miscellaneous Problems of Time Complexity
Guidelines for asymptotic analysis Guidelines for asymptotic analysis
Why integer size varies from computer to computer? Why integer size varies from computer to computer?
Subdomain takeover from scratch to advance Subdomain takeover from scratch to advance

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje