Partitioning An Array Into Two Parts For Maximizing Area

Brute Force Approach

The problem boils down to partition the array into two parts such that the such that the overall anwer is the individual sum of the area in those parts.The area of the parts are calculated as minimum height of the element in that part and the width of that part , were width is the number of elements in that part. 

Brute force approach is that in this problem we have to partition this array into two parts such that the area formed by the two parts is maximized. The area is calculated by taking the minimum height in each part multiplied by the number of heights in the corresponding path. 

Pseudocode 

1. Max_area=0
2. loop i from 1 to n-1
3. left_count=i
4. right_count=n-i
5. minimum_left=min(arr,0,i) # get the minimum element in the array from index 0 to i-1
6. minimum_right=min(arr,i,n) # get the minimum element in the array from index i to n-1
7. total_current_area=(minimum_left*left_count)+(minimum_right*right_count)
8. Maxarea=maximum_of(Max_area,total_current_area)
9. print(Maxarea)
10. Time Complexity of this approach is o(N*N), where N is the length of the array,Two loops are used one for traversing the array and other for getting the minimum in both parts

Python implementation of the brute force solution 

from array import*

maxint = 9999999 

arr=array('i',[])

n=int(input())

#taking the array input

arr = list(map(int , input().rstrip().split(" "))) 

# declaring the max area initially 0

max_Area=0 

#implementing the brute force approach

for i in range(1,n-1):

    # initializing the min_left and min_right a big integer we can also

    # initialize maximum integer available in python

    min_left =  maxint

    min_right= maxint 

    # count_left is the left window or left partition size

    # count_right is the right window or right partition size

    count_left=i

    count_right=n-(i) 

    # calculating the min_left

    for j in range(0,i):

       if(arr[j]<min_left):

            min_left=arr[j] 

    # calculating the min_right       

    for j in range(i,n):

       if(arr[j]<min_right):

            min_right=arr[j] 

    #after calculating the min_right and min_left

    # The Total area obtained is the sum of  area formed by the left and right part

    total_area=(min_left*count_left)+(min_right*count_right) 

    # if the total_area here is greater than the max_Area so far then we update our max_Area answer

    if(max_Area<total_area):

        max_Area=total_area 

print(max_Area) 

Yes. There is a more efficient way is available in which we store the prefix minimum(This array will store the  minimum element the prefix array has for every index ) and suffix minimum(This array will store the  minimum element the suffix array has for every index ) instead of searching for minimum in the left and right part which was previously done in o(N) now it will be done in o(1) time so the time complexity of the problem turn out to be O(N) and space complexity O(N). 

# Suffix array and prefix array have the same size as that of input array

1. suff_min_arr[]
2. pref_min_arr[]

# maintaining prefix min array

1. minel=arr[0] (Minel stores the minimum element )
2. for i from (0 to n-1)
3. minel=min(minel,arr[i])
4. pref_min_arr[i]=minel

# maintaining suffix min array

1. minel=arr[n-1]
2. for i from (n-1 to 0)
3. minel=min(minel,arr[i])
4. suff_min_arr[i]=minel

# Calculating max area formed

1. Max_area=0
2. for i from(1,to n-1)
3. count_left=i
4. count_right=n-i
5. minimum_left=pref_min_arr[i-1]
6. minimum_right=suff_min_arr[i]
7. totaLcurrent_area=(minimum_left*count_left)+(minimum_right*count_right)
8. Max_area=maximum_of(Max_area,total_current_area)
9. print(Max_area) 

d)The first solution uses two loops and for every i we partition list from 0 to i-1 and from i to n-1 we calculate the minimum height for both the partition by traversing each part and overall traversal time is o(N) for every i we take o(N) time and there are N different i so the time complexity becomes o(N*N) 

While in the second solution the minimum of both the parts is calculated using prefix and suffix minimum array that takes O(1) time for calculation so the time complexity becomes o(N) and space complexity O(N) for maintaining prefix and suffix array

Efficient Approach Using Prefix and Suffix Minimum Arrays

The brute force solution will be to sort the first array in ascending order and sort the other array in descending order. Then for the given value of K, we check the K largest element from the second array and will replace K minimum element if they are larger than the first array element. 

Pseudocode 

1. Take the input for n , k and arr1 and arr2
2. Sort arr1 ascendingly O(nlogn)
3. Sort arr2 descendingly O(nlogn)
4. For the range K take iterate over the first array.

For a value i of the first array , the value j from the second array is greater than, replace the element i in arr1 with j, increment the indexes.

if i > j , then all the rest elements of arr2 will be less than arr1 elements from index i..end , so break the loop.

Print the sum of the arr1. 

Overall time complexity : 2*O(nlogn) + O(K) + O(n)  = O(nlogn) 

The above solution can be improved by using heap instead of sorting the array, for the solution we have to use two types of heap , a MaxHeap and a MinHeap , a MaxHeap can retrieve the largest element of a set of elements in O(1) time complexity , and building a heap take O(logN) time.

Pseudocode 

1. Take the input for n, k and arr1 and arr2.
2. Make a min heap for arr1
3. Make a max heap for arr2
4. For the range k,

4.1 take out  the minimum value from arr1( val1 ) and get the maximum value from arr2(val2).

4.2 If val1 < val2 , insert val2 in arr1 and if not insert val1 back in arr1.

Print the sum of arr1 inside the heap.

Overall time complexity: 2*O(logn) + k*O(1 + logN) + O(N) = O(N)+k*O(logN) = O(N)

Python implementation

import heapq

class MinHeap: 

  def __init__(self , arr):

    self.arr = arr

    self.len = len(arr)

    heapq.heapify(arr) 

  def pop(self):

    return heapq.heappop(self.arr)

  def push(self , elem):

    return heapq.heappush(self.arr ,elem ) 

  def sum(self):

    return sum(self.arr) 

class MaxHeap: 

  def __init__(self , arr):

    self.arr = [-1 * elem for elem in arr]

    self.len = len(arr)

    heapq.heapify(self.arr) 

  def pop(self):

    return -1*heapq.heappop(self.arr)

  def push(self , elem):

    return heapq.heappush(self.arr ,-1*elem )

  def sum(self):

    return sum(self.arr)   

rv=list(map(int,input().split()))

n,k=rv[0],rv[1]

a=list(map(int,input().split()))

b=list(map(int,input().split()))  

heap_a = MinHeap(a)

heap_b = MaxHeap(b)

for i in range(k):

  val1 = heap_a.pop()

  val2 = heap_b.pop() 

  if val2 > val1:

    heap_a.push(val2)

  else:

    heap_a.push(val1)

print(heap_a.sum()) 

The brute force solution uses sorting to solve the problem by sorting the arrays in a ascending and descending order , and then it compares and matches the elements from both the arrays, the improvement on this solution could be to sort only the arrays upto K elements only, as only those are required. 

The second solution is more efficient as it uses heaps to get the largest or the smallest element in O(1) time , and inserting an element to a heap takes O(logN) times. Overall the algorithm takes the worst time complexity of O(N) to sum up the array elements.   

Brute force algorithm: 

Algorithm 

1. Check if the array size is less than 2, then, either the array is empty or it has one element so, a pair is not possible.
2. If array length is greater than 2, then, iterate over the array twice to take one element and then compute the product of this element with other elements in the array, if the product is greater than the previous highest product then replace a and b with the new numbers.
3. Loop over each element and compute the products, finally the max product can be found 

Pseudocode: 

func maxProduct(arr, arr_size): 

if (arr_size < 2):

print("Pair does not exist")

return    

    # Initialize max product pair

    a = arr[0]; b = arr[1] 

    for i in range(0, arr_size):   

Comparison of Time and Space Complexities

        for j in range(i + 1, arr_size):

            if (arr[i] * arr[j] > a * b):

a = arr[i]; b = arr[j]

    print("Max product is: ", a*b) 

Code: 

# Function to return the max product of a pair in array

def maxProduct(arr, arr_size):

  if (arr_size < 2):

      print("Pair does not exist")

      return

  # Initializing the pair

  a = arr[0]; b = arr[1]

  # Traversing through each possible pair to find the max product

  for i in range(0, arr_size):      

      for j in range(i + 1, arr_size):

          if (arr[i] * arr[j] > a * b):

              a = arr[i]; b = arr[j]

  print("Max product is: ", a*b)

# Taking array input and passing the arr into function

arr = [int(item) for item in input("Enter the list items : ").split()]

arr_size = len(arr)

maxProduct(arr, arr_size)

Complexity of the brute force algorithm is O(n^2) as the array is iterated twice to find the pair with maximum product, the first pointer runs through the length of the array from 0 to end, while the other pointer runs ahead of the first pointer by 1 and then iterates till end of the array leading to this time complexity. 

1. b) Sorting the array and then getting product of highest two integers:

1. Sort the array.
2. Check for the smallest integer numbers-first two integers (negative integers with highest absolute values) in the sorted array and compute the product.
3. Check for the largest integer numbers- last 2 integers (positive integers with highest absolute values) in the sorted array and compute the product
4. Compare if the product of first two numbers (negative integers) is greater than the product of last two numbers (positive numbers) and vice-versa to get the pair of numbers with maximum product.

Pseudocode:

   # Calculating the product of two smallest numbers

    prod1 = arr[0] * arr[1]

    # Calculating the product of two largest numbers

    prod2 = arr[arr_size - 1] * arr[arr_size - 2]

    # Printing the pair with greatest product

    if (prod1 > prod2):

        num1 = arr[0]

        num2 = arr[1]

    else:

        num1 = arr[arr_size - 2]

        num2 = arr[arr_size - 1]

    print("Max product is: ", num1*num2)

Code:

def maxProduct(arr, arr_size):

   # Sorting the array

   arr.sort()

   num1 = num2 = 0

   # As the array has both positive and negative numbers so

   # largest and smallest both pair products are to be considered

   # Calculating the product of two smallest numbers

   prod1 = arr[0] * arr[1]

   # Calculating the product of two largest numbers

   prod2 = arr[arr_size - 1] * arr[arr_size - 2]

   # Printing the pair with greatest product

   if (prod1 > prod2):

       num1 = arr[0]

       num2 = arr[1]

else:

       num1 = arr[arr_size - 2]

       num2 = arr[arr_size - 1]

   print("Max product is: ", num1*num2)

# Taking array input and passing the array into function

arr = [int(item) for item in input("Enter the list items : ").split()]

arr_size = len(arr)

maxProduct(arr, arr_size)

This is definitely a better approach as compared to brute force as it takes O(nlogn) time complexity while brute force takes O(n^2) as this approach sorts the array.

Extreme cases to be considered while designing algorithm

The extreme cases that are to be considered while designing the solution to this problem is considering negative numbers. It is possible that the product of two negative numbers with higher absolute value than positive number can result in a higher product value when compared to taking the largest positive integers and computing their product.

For example: Consider this array [-14 7 9 10 -10 4]

After sorting the array becomes  = [-14 -10 4 7 9 10] 

The product of the pair of largest positive integers here will result in = 90 while.

The product of the pair of smallest negative integers here will result in = 140

It is clear that, 140 > 90, so the product of the pair of smallest negative integers is more than the pair of largest positive integers.

So, smallest negative integers are to be considered while designing the solution to this problem.

Own idea to solve this problem with O(n) time complexity

Idea to solve this problem in an O(n) solution can be to traverse the array two times and take a store of four values, largest , second_largest , minimum and second_minimum.At the end we compare the product of minimum and second_minimum and the product of maximum and second_maximum.

Pseudocode

1. Get the minimum and maximum elements of the array on the first traversal.
2. On the second traversal, get the second maximum and second minimum element of the array by comparing the maximum and minimum element of the first traversal.
3. Compute the products of least elements and large elements and display the maximum product.

count = 0

for i = 1 to n do

 for k = 1 to n do

  for (j = 2 ; j < n ; j *= 2)

     count = i + k + j;

 end for

end for

end for

Solution :

Here the first loop runs for n time and the second  loop also runs for n times and the third loop runs for logn times ..

So when we  count the number of times inner most loop execute is n*n*logn times

So we can say that total time complexity of the given program is O(n^2logn(base2)) 

2):

count = 1

for i = 1 to n do

 count += i

for k = 1 to n do

 count *= k

    k +=2

    while j < n do

      count +=j

        j *= 2;

end while

Solution :-

Here the first loop run for n times 2nd  loop run for n times 

After analysing the question recurrence relation form is

T(n)=64T(n/8)+O(n^2)

And if you solve it by master theorem we get time complexity as O(n^2)

Here the subproblem solved by calling n-1 and then combining Q(n) 

Sowe make the recurrence relation as

T(n)=T(n-1)+n

If we calculate by using Iterative method to solve the relation  we get time complexity as

O(n^2)

5)

T(n)=8T(n/4)+n

Solving it by Master Theorem we get

Time complexity as O(n^3/2)