Split Array Largest Sum – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given an array nums
which consists of non-negative integers and an integer m
, you can split the array into m
non-empty continuous subarrays.
Write an algorithm to minimize the largest sum among these m
subarrays.
Example 1:
Input: nums = [7,2,5,10,8], m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
Example 2:
Input: nums = [1,2,3,4,5], m = 2 Output: 9
Example 3:
Input: nums = [1,4,4], m = 3 Output: 4
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)
C++ Split Array Largest Sum LeetCode Solution
int splitArray(vector<int>& nums, int m) {
int l=0,r=0,n=nums.size();
for(int i=0;i<n;++i) l=max(l,nums[i]), r+=nums[i];
int mid=0,ans=0;
while(l<=r){
mid=(l+r)/2;
int count=0,tempsum=0;
for(int i=0;i<n;++i){
if(tempsum+nums[i]<=mid) tempsum+=nums[i];
else count++,tempsum=nums[i];
}
count++;
if(count<=m) r=mid-1, ans=mid;
else l=mid+1;
}
return ans;
}
Java Split Array Largest Sum LeetCode Solution
class Solution {
int[] nums;
public int splitArray(int[] nums, int m) {
this.nums = nums;
int low = 0, high = 0, min = Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++){
low = Math.max(low, nums[i]);
high += nums[i];
}
while(low <= high) {
int mid = (low + high) / 2;
if(required_no_of_chunks(mid, m)){
min = Math.min(min, mid);
high = mid - 1;
}
else low = mid + 1;
}
return min;
}
private boolean required_no_of_chunks(int mid, int m){
int chunks = 0, i=0;
while(i < nums.length){
int val = 0;
while(i < nums.length && nums[i] + val <= mid) val += nums[i++];
chunks++;
}
return chunks <= m;
}
}
Python 3 Split Array Largest Sum LeetCode Solution
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo+hi)//2
tot, cnt = 0, 1
for num in nums:
if tot+num<=mid:
tot += num
else:
tot = num
cnt += 1
if cnt>m: lo = mid+1
else: hi = mid
return hi
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1