Maximize the minimum array element by M subarray increments of size S

0 0 8 minutes read

Given an array arr[] of N integers and two integers S and M, the task is to maximize the minimum array element by incrementing any subarray of size S by 1, M number of times.

Examples:

Input: arr[] = {1, 2, 3, 4, 5, 6}, S = 2, M = 3
Output: 3
Explanation:
Below are the operations performed:
Operation 1: Select subarray {1, 2} and after increment, array arr[] becomes = {2, 3, 3, 4, 5, 6}.
Operation 2: Select subarray {2, 3} and after increment, array arr[] becomes = {3, 4, 3, 4, 5, 6}.
Operation 3: Select subarray {3, 4} and after increment, array arr[] becomes = {4, 5, 3, 4, 5, 6}.
After the above operations, the minimum element of the array is 3.

Input: arr[] = {3, 5, 2, 7, 3}, S = 3, M = 3
Output: 4
Explanation:
Below are the operations performed:
Operation 1: Select subarray {3, 5, 2} and after increment, array arr[] becomes = {4, 6, 3, 7, 3}.
Operation 2: Select subarray {4, 6, 3} and after increment, array arr[] becomes = {5, 7, 4, 7, 3}.
Operation 3: Select subarray {4, 7, 3} and after increment, array arr[] becomes = {5, 7, 5, 8, 4}.
After the above operations, the minimum element of the array is 4.

Approach: The idea is to find the minimum element of the array M number of times and increment subarrays of size S from that minimum element by 1. Follow the steps below to solve the problem:

Traverse over the array M number of times and for each iteration do the following:
- Find the minimum element of the array arr[]. Let the first index of the minimum element be idx.
- Increment the current minimum element by 1.
- Now take two pointers leftIdx as idx – 1 and rightIdx as idx + 1.
- If the element at leftIdx is less than the element at rightIdx then increment A[leftIndex] by 1 and decrement leftIndex by 1. Otherwise, increment A[rightIndex] by 1 and rightIndex by 1. Continue this step till (S – 1) elements are processed.
After the above iterations, print the minimum element of the updated array.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return index of minimum
// element in the array
int min(int a[], int n)
{
    // Initialize a[0] as minValue
    int minIndex = 0, minValue = a[0], i;
 
    // Traverse the array
    for (i = 1; i < n; i++) {
 
        // If a[i] < existing minValue
        if (a[i] < minValue) {
            minValue = a[i];
            minIndex = i;
        }
    }
 
    // Return the minimum index
    return minIndex;
}
 
// Function that maximize the minimum
// element of array after incrementing
// subarray of size S by 1, M times
int maximizeMin(int A[], int N,
                int S, int M)
{
    int minIndex, left, right, i, j;
 
    // Iterating through the array
    // for M times
    for (i = 0; i < M; i++) {
 
        // Find minimum element index
        minIndex = min(A, N);
 
        // Increment the minimum value
        A[minIndex]++;
 
        // Storing the left index
        // and right index
        left = minIndex - 1;
        right = minIndex + 1;
 
        // Incrementing S - 1 minimum
        // elements to the left and
        // right of minValue
        for (j = 0; j < S - 1; j++) {
 
            // Reached extreme left
            if (left == -1)
                A[right++]++;
 
            // Reached extreme right
            else if (right == N)
                A[left--]++;
 
            else {
 
                // Left value is minimum
                if (A[left] < A[right])
                    A[left--]++;
 
                // Right value is minimum
                else
                    A[right++]++;
            }
        }
    }
 
    // Find the minValue in A[] after
    // M operations
    minIndex = min(A, N);
 
    // Return the minimum value
    return A[minIndex];
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int S = 2, M = 3;
 
    // Function Call
    cout << maximizeMin(arr, N, S, M);
 
    return 0;
}

Java

// Java program for the 
// above approach
import java.util.*;
class solution{
 
// Function to return index
// of minimum element in the 
// array
static int min1(int a[], int n)
{
  // Initialize a[0] as 
  // minValue
  int minIndex = 0,
      minValue = a[0], i;
 
  // Traverse the array
  for (i = 1; i < n; i++) 
  {
    // If a[i] < existing
    // minValue
    if (a[i] < minValue) 
    {
      minValue = a[i];
      minIndex = i;
    }
  }
 
  // Return the minimum index
  return minIndex;
}
 
// Function that maximize the minimum
// element of array after incrementing
// subarray of size S by 1, M times
static int maximizeMin(int A[], int N, 
                       int S, int M)
{
  int minIndex, left, right, i, j;
 
  // Iterating through the 
  // array or M times
  for (i = 0; i < M; i++) 
  {
    // Find minimum element 
    // index
    minIndex = min1(A, N);
 
    // Increment the minimum 
    // value
    A[minIndex]++;
 
    // Storing the left index
    // and right index
    left = minIndex - 1;
    right = minIndex + 1;
 
    // Incrementing S - 1 minimum
    // elements to the left and
    // right of minValue
    for (j = 0; j < S - 1; j++) 
    {
      // Reached extreme left
      if (left == -1)
        A[right++]++;
 
      // Reached extreme right
      else if (right == N)
        A[left--]++;
 
      else
      {
        // Left value is minimum
        if (A[left] < A[right])
          A[left--]++;
 
        // Right value is minimum
        else
          A[right++]++;
      }
    }
  }
 
  // Find the minValue in A[] after
  // M operations
  minIndex = min1(A, N);
 
  // Return the minimum value
  return A[minIndex];
}
 
// Driver Code
public static void main(String args[])
{
  int []arr = {1, 2, 3, 
               4, 5, 6};
  int N = arr.length;
  int S = 2, M = 3;
 
  // Function Call
  System.out.print(maximizeMin(arr, N, S, M));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

Python3

# Python3 program for the above approach
 
# Function to return index of minimum
# element in the array
def min(a, n):
     
    # Initialize a[0] as minValue
    minIndex = 0
    minValue = a[0]
 
    # Traverse the array
    for i in range(1, n):
         
        # If a[i] < existing minValue
        if (a[i] < minValue):
            minValue = a[i]
            minIndex = i
 
    # Return the minimum index
    return minIndex
 
# Function that maximize the minimum
# element of array after incrementing
# subarray of size S by 1, M times
def maximizeMin(A, N, S, M):
     
    minIndex, left, right = 0, 0, 0
     
    # Iterating through the array
    # for M times
    for i in range(M):
         
        # Find minimum element index
        minIndex = min(A, N)
 
        # Increment the minimum value
        A[minIndex] += 1
 
        # Storing the left index
        # and right index
        left = minIndex - 1
        right = minIndex + 1
 
        # Incrementing S - 1 minimum
        # elements to the left and
        # right of minValue
        for j in range(S - 1):
             
            # Reached extreme left
            if (left == -1):
                A[right] += 1
                right += 1
                 
            # Reached extreme right
            elif (right == N):
                A[left] += 1
                left -= 1
 
            else:
 
                # Left value is minimum
                if (A[left] < A[right]):
                    A[left] += 1
                    left -= 1
                     
                # Right value is minimum
                else:
                    A[right] += 1
                    right += 1
 
    # Find the minValue in A[] after
    # M operations
    minIndex = min(A, N)
 
    # Return the minimum value
    return A[minIndex]
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 2, 3, 4, 5, 6 ]
    N = len(arr)
    S = 2
    M = 3
     
    #Function Call
    print(maximizeMin(arr, N, S, M))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the 
// above approach
using System;
class GFG{
     
// Function to return index
// of minimum element in the 
// array
static int min1(int[] a, 
                int n)
{
  // Initialize a[0] as 
  // minValue
  int minIndex = 0, 
      minValue = a[0], i;
 
  // Traverse the array
  for (i = 1; i < n; i++) 
  {
    // If a[i] < existing
    // minValue
    if (a[i] < minValue) 
    {
      minValue = a[i];
      minIndex = i;
    }
  }
 
  // Return the minimum 
  // index
  return minIndex;
}
      
// Function that maximize the 
// minimum element of array 
// after incrementing subarray 
// of size S by 1, M times
static int maximizeMin(int[] A, int N, 
                       int S, int M)
{
  int minIndex, left, right, i, j;
 
  // Iterating through the 
  // array or M times
  for (i = 0; i < M; i++) 
  {
    // Find minimum element 
    // index
    minIndex = min1(A, N);
 
    // Increment the minimum 
    // value
    A[minIndex]++;
 
    // Storing the left index
    // and right index
    left = minIndex - 1;
    right = minIndex + 1;
 
    // Incrementing S - 1 minimum
    // elements to the left and
    // right of minValue
    for (j = 0; j < S - 1; j++) 
    {
      // Reached extreme left
      if (left == -1)
        A[right++]++;
 
      // Reached extreme right
      else if (right == N)
        A[left--]++;
 
      else
      {
        // Left value is minimum
        if (A[left] < A[right])
          A[left--]++;
 
        // Right value is minimum
        else
          A[right++]++;
      }
    }
  }
 
  // Find the minValue in A[] after
  // M operations
  minIndex = min1(A, N);
 
  // Return the minimum value
  return A[minIndex];
}
   
// Driver code
static void Main() 
{
  int[] arr = {1, 2, 3, 
               4, 5, 6};
  int N = arr.Length;
  int S = 2, M = 3;
 
  // Function Call
  Console.Write(maximizeMin(arr, N, 
                            S, M));
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to return index
// of minimum element in the
// array
function min1(a, n)
{
  // Initialize a[0] as
  // minValue
  let minIndex = 0,
      minValue = a[0], i;
  
  // Traverse the array
  for (i = 1; i < n; i++)
  {
    // If a[i] < existing
    // minValue
    if (a[i] < minValue)
    {
      minValue = a[i];
      minIndex = i;
    }
  }
  
  // Return the minimum index
  return minIndex;
}
  
// Function that maximize the minimum
// element of array after incrementing
// subarray of size S by 1, M times
function maximizeMin(A, N, S, M)
{
  let minIndex, left, right, i, j;
  
  // Iterating through the
  // array or M times
  for (i = 0; i < M; i++)
  {
    // Find minimum element
    // index
    minIndex = min1(A, N);
  
    // Increment the minimum
    // value
    A[minIndex]++;
  
    // Storing the left index
    // and right index
    left = minIndex - 1;
    right = minIndex + 1;
  
    // Incrementing S - 1 minimum
    // elements to the left and
    // right of minValue
    for (j = 0; j < S - 1; j++)
    {
      // Reached extreme left
      if (left == -1)
        A[right++]++;
  
      // Reached extreme right
      else if (right == N)
        A[left--]++;
  
      else
      {
        // Left value is minimum
        if (A[left] < A[right])
          A[left--]++;
  
        // Right value is minimum
        else
          A[right++]++;
      }
    }
  }
  
  // Find the minValue in A[] after
  // M operations
  minIndex = min1(A, N);
  
  // Return the minimum value
  return A[minIndex];
}
  
 
// Driver Code
 
    let arr = [1, 2, 3,
               4, 5, 6];
  let N = arr.length;
  let S = 2, M = 3;
  
  // Function Call
  document.write(maximizeMin(arr, N, S, M));
           
</script>

Output:

Time Complexity: O(M*N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!