CODEWITHSUNDEEP
algorithmpartitioningquickselect
Nati Shen-Gordon
Nati Shen-Gordon

Reputation: 35

Divide an array into 2 subarray considering keys and weights

Let there be an array A with n elements. Every element in A has a key, and a weight.

Divide A into 2 subarrays (does not have to be of equal size), where every key in group 1 is smaller than every key in group 2, and the total weight of both subarrays must be equal.

Time Complexity : O(n) in the worst case scenerio.

I've tried using the quick SELECT algorithm and partitioning the array by key values. that gives us 2 subarrays in which every key is subarray 1 is smaller than subarray 2. If weights are not equal, we'll need to move the biggest key element into the other subarray and then compare weights. The issue is, finding biggest key element every time takes n/2 + (n/2)-1... which is O(n^2).

Upvotes: 1

Views: 75

Answers (0)

Related Questions