Given an array A[] of N integers. The task is to partition the array into four non-empty contiguous subarrays P, Q, R, and S such that each element of the array A[] should be present in any subarray.
Let W, X, Y, and Z be the sum of the elements in P, Q, R, and S respectively.
Find the smallest absolute difference between the maximum and the minimum among W, X, Y, and Z.
Example 1:
Input:
N = 5
A[] = [4,2,2,5,1]
Output: 4
Explanation: let partition the array 
P,Q,R,S = [4],[2,2],[5],[1]
W = 4, X = 4, Y = 5, Z = 1 
Differnce = max(W,X,Y,Z)-min(W,X,Y,Z)= 5-1 = 4 
Example 2:
Input:
N = 4
A[] = {4,4,4,4}
Output: 0
Explanation: 
There is only one way to partition 
the array. P,Q,R,S = [4],[4],[4],[4]
Your Task:
You don't need to read input or print anything. The task is to complete the function minDifference() which takes the integer N and the array A[] as inputs and returns the smallest absolute difference.
Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(N)
Constraints:
4 < N < 10^{5}
1 < A[i] < 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Sorting

Amortized analysis

Starter code: #User function Template for python3

class Solution:

    def minDifference(self, N, A): 

        #code here



Solutions:
class Solution:

	def minDifference(self, N, A):
		x = self.partition(A, N)
		A.reverse()
		y = self.partition(A, N)
		y.reverse()
		ans = 10 ** 18
		for i in range(1, N - 2):
			ans = min(ans, max(x[i][0], x[i][1], y[i + 1][0], y[i + 1][1]) - min(x[i][0], x[i][1], y[i + 1][0], y[i + 1][1]))
		return ans

	def partition(self, A, n):
		tmp = [(0, 0)]
		p = A[:]
		for i in range(1, n):
			p[i] += p[i - 1]
		for i in range(1, n):
			diff = 10 ** 18
			hi = i
			lo = 1
			ans = (0, 0)
			while lo <= hi:
				mid = (lo + hi) // 2
				x = p[mid - 1]
				y = p[i] - x
				if abs(x - y) < diff:
					diff = abs(x - y)
					ans = (x, y)
				if x > y:
					hi = mid - 1
				else:
					lo = mid + 1
			tmp.append(ans)
		return tmp


class Solution:

	def minDifference(self, N, A):
		sums = [0] * (N + 1)
		for (i, e) in enumerate(A):
			sums[i + 1] = sums[i] + e

		def search(l, r):
			(lo, hi) = (l, r)
			while lo < hi:
				m = lo + (hi - lo) // 2
				lp = sums[m + 1] - sums[l]
				rp = sums[r + 1] - sums[m]
				if lp >= rp:
					hi = m
				else:
					lo = m + 1
			(v1, v2) = (sums[lo + 1] - sums[l], sums[r + 1] - sums[lo + 1])
			if lo > l:
				(v3, v4) = (sums[lo] - sums[l], sums[r + 1] - sums[lo])
				if abs(v2 - v1) > abs(v4 - v3):
					return (min(v3, v4), max(v3, v4))
			return (min(v1, v2), max(v1, v2))
		ans = float('inf')
		for i in range(1, N - 2):
			(minv1, maxv1) = search(0, i)
			(minv2, maxv2) = search(i + 1, N - 1)
			ans = min(ans, max(maxv1, maxv2) - min(minv1, minv2))
		return ans


class Solution:

	def minDifference(self, N, A):

		def _split(L, R):
			LSUM = acc[L - 1] if L > 0 else 0
			tot = acc[R] - LSUM
			goal = tot // 2
			while L < R:
				m = (L + R) // 2
				if acc[m] - LSUM < goal:
					L = m + 1
				else:
					R = m
			(v1, v2) = (acc[L] - LSUM, tot - (acc[L] - LSUM))
			if L > 0:
				(v3, v4) = (acc[L - 1] - LSUM, tot - (acc[L - 1] - LSUM))
				if abs(v2 - v1) > abs(v4 - v3):
					return (v3, v4)
			return (v1, v2)
		from itertools import accumulate
		acc = list(accumulate(A))
		ans = 10 ** 9
		for i in range(1, N - 2):
			(W, X) = _split(0, i)
			(Y, Z) = _split(i + 1, N - 1)
			vs = sorted((W, X, Y, Z))
			ans = min(ans, vs[3] - vs[0])
		return ans


class Solution:

	def find_split(self, a):
		n = len(a)
		prefix_sum = [0] * (n + 1)
		for i in range(n):
			prefix_sum[i] = a[i]
			if i > 0:
				prefix_sum[i] += prefix_sum[i - 1]
		split_points = [[0, 0]]
		for i in range(1, n):
			(low, high) = (1, i)
			min_diff = 2e+18
			split = [0, 0]
			while low <= high:
				mid = (low + high) // 2
				x = prefix_sum[mid - 1]
				y = prefix_sum[i] - x
				if abs(x - y) < min_diff:
					min_diff = abs(x - y)
					split[0] = x
					split[1] = y
				if x > y:
					high = mid - 1
				else:
					low = mid + 1
			split_points.append(split)
		return split_points

	def minDifference(self, N, A):
		ans = 2e+18
		x = self.find_split(A)
		y = self.find_split(A[::-1])[::-1]
		for i in range(1, N - 2):
			ans = min(ans, max(max(x[i][0], x[i][1]), max(y[i + 1][0], y[i + 1][1])) - min(min(x[i][0], x[i][1]), min(y[i + 1][0], y[i + 1][1])))
		return ans


class Solution:

	def minDifference(self, N, A):
		su = [0] * (N + 1)
		for (i, e) in enumerate(A):
			su[i + 1] = su[i] + e

		def b_search(l, r):
			(low, high) = (l, r)
			while low < high:
				m = low + (high - low) // 2
				lp = su[m + 1] - su[l]
				rp = su[r + 1] - su[m]
				if lp >= rp:
					high = m
				else:
					low = m + 1
			(v1, v2) = (su[low + 1] - su[l], su[r + 1] - su[low + 1])
			if low > l:
				(v3, v4) = (su[low] - su[l], su[r + 1] - su[low])
				if abs(v2 - v1) > abs(v4 - v3):
					return (min(v3, v4), max(v3, v4))
			return (min(v1, v2), max(v1, v2))
		ans = float('inf')
		for i in range(1, N - 2):
			(minv1, maxv1) = b_search(0, i)
			(minv2, maxv2) = b_search(i + 1, N - 1)
			ans = min(ans, max(maxv1, maxv2) - min(minv1, minv2))
		return ans


class Solution:

	def minmax(self, A, l, h):
		low = l
		high = h
		while low < high:
			mid = low + (high - low) // 2
			lsum = A[mid + 1] - A[l]
			rsum = A[h + 1] - A[mid]
			if lsum >= rsum:
				high = mid
			else:
				low = mid + 1
		(v1, v2) = (A[low + 1] - A[l], A[h + 1] - A[low + 1])
		if low > l:
			(v3, v4) = (A[low] - A[l], A[h + 1] - A[low])
			if abs(v2 - v1) > abs(v4 - v3):
				return [min(v3, v4), max(v3, v4)]
		return [min(v1, v2), max(v1, v2)]

	def minDifference(self, N, A):
		prefixSum = [0]
		for i in range(1, len(A) + 1):
			prefixSum.append(prefixSum[i - 1] + A[i - 1])
		ans = float('inf')
		for i in range(1, N - 2):
			left = self.minmax(prefixSum, 0, i)
			right = self.minmax(prefixSum, i + 1, N - 1)
			ans = min(ans, max(left[1], right[1]) - min(left[0], right[0]))
		return ans


from itertools import chain

class Solution:

	def minDifference(self, N, A):

		def get_prefix_sums(arr):
			n = len(arr)
			sums = [0] * n
			sums[0] = arr[0]
			for i in range(1, n):
				sums[i] = sums[i - 1] + arr[i]
			return sums

		def find_center_of_mass(prefix_sums, start, end):
			pre_sum = 0
			if start > 0:
				pre_sum = prefix_sums[start - 1]
			sums = [prefix_sums[start] - pre_sum, prefix_sums[end] - prefix_sums[start]]
			diff = abs(sums[0] - sums[1])
			(left, right) = (start, end)
			while left != right:
				mid = left + (right - left) // 2
				left_sum = prefix_sums[mid] - pre_sum
				right_sum = prefix_sums[end] - prefix_sums[mid]
				new_diff = abs(left_sum - right_sum)
				if new_diff < diff:
					sums = [left_sum, right_sum]
					diff = new_diff
				if left_sum < right_sum:
					left = mid + 1
				else:
					right = mid
			return sums
		prefix_sums = get_prefix_sums(A)
		min_diff = float('inf')
		for i in range(1, N - 2):
			left_sums = find_center_of_mass(prefix_sums, 0, i)
			right_sums = find_center_of_mass(prefix_sums, i + 1, N - 1)
			min_diff = min(min_diff, abs(min(chain(left_sums, right_sums)) - max(chain(left_sums, right_sums))))
		return min_diff


class Solution:

	def helper(self, i, j, reduction):
		(x, y) = (i, j)
		score = float('inf')
		best = 0
		MaxVal = self.subA[j - 1]
		while x < y:
			mid = (x + y) // 2
			subres = MaxVal - 2 * self.subA[mid] + reduction
			abssubres = abs(subres)
			if abssubres < score:
				score = abssubres
				best = mid
			if subres == 0:
				(x, y) = (y, x)
				continue
			if subres > 0:
				(x, y) = (mid + 1, y)
				continue
			else:
				(x, y) = (x, mid)
		return (self.subA[best] - reduction, MaxVal - self.subA[best])

	def minDifference(self, N, A):
		res = float('inf')
		subSum = 0
		self.subA = [0] * N
		for (ind, value) in enumerate(A):
			subSum += value
			self.subA[ind] = subSum
		for i in range(2, N - 1):
			(L1, L2) = self.helper(0, i, 0)
			(R1, R2) = self.helper(i, N, self.subA[i - 1])
			score = max(L1, L2, R1, R2) - min(L1, L2, R1, R2)
			res = min(res, score)
		return res


class Solution:

	def minDifference(self, n, arr):
		summ = [0] * (n + 1)
		for (i, e) in enumerate(arr):
			summ[i + 1] = summ[i] + e

		def parts(l, r):
			(low, high) = (l, r)
			while low < high:
				m = low + (high - low) // 2
				lp = summ[m + 1] - summ[l]
				rp = summ[r + 1] - summ[m]
				if lp >= rp:
					high = m
				else:
					low = m + 1
			(v1, v2) = (summ[low + 1] - summ[l], summ[r + 1] - summ[low + 1])
			if low > l:
				(v3, v4) = (summ[low] - summ[l], summ[r + 1] - summ[low])
				if abs(v2 - v1) > abs(v4 - v3):
					return (min(v3, v4), max(v3, v4))
			return (min(v1, v2), max(v1, v2))
		res = float('inf')
		for i in range(1, N - 2):
			(minv1, maxv1) = parts(0, i)
			(minv2, maxv2) = parts(i + 1, N - 1)
			res = min(res, max(maxv1, maxv2) - min(minv1, minv2))
		return res


from itertools import accumulate

class Solution:

	def minDifference(self, N, A):

		def maxMin(prefixSum, L, R):
			LSUM = prefixSum[L - 1] if L > 0 else 0
			tot = prefixSum[R] - LSUM
			goal = tot // 2
			while L < R:
				m = (L + R) // 2
				if prefixSum[m] - LSUM < goal:
					L = m + 1
				else:
					R = m
			(v1, v2) = (prefixSum[L] - LSUM, tot - (prefixSum[L] - LSUM))
			if L > 0:
				(v3, v4) = (prefixSum[L - 1] - LSUM, tot - (prefixSum[L - 1] - LSUM))
				if abs(v2 - v1) > abs(v4 - v3):
					return (v3, v4)
			return (v1, v2)
		prefixSum = list(accumulate(A))
		ans = 10 ** 9
		for i in range(1, N - 2):
			maxMinLeft = maxMin(prefixSum, 0, i)
			maxMinRight = maxMin(prefixSum, i + 1, N - 1)
			value = max(maxMinLeft[1], maxMinRight[1], maxMinLeft[0], maxMinRight[0]) - min(maxMinLeft[0], maxMinRight[0], maxMinLeft[1], maxMinRight[1])
			ans = min(ans, value)
		return ans


class Solution:

	def minDifference(self, N, A):
		arr = [0] * N
		arr[0] = A[0]
		for i in range(1, N):
			arr[i] = A[i] + arr[i - 1]
		ans = float('inf')
		for i in range(2, N - 1):
			index = self.binary_search(arr, 0, i - 1, arr[i - 1], 0)
			w = arr[index]
			x = arr[i - 1] - w
			index = self.binary_search(arr, i, N - 1, arr[N - 1], arr[i - 1])
			y = arr[index] - arr[i - 1]
			z = arr[N - 1] - arr[index]
			ans = min(ans, max(w, x, y, z) - min(w, x, y, z))
		return ans

	def binary_search(self, arr, low, high, _sum, temp):
		(mid, index) = (-1, -1)
		(first, second, diff) = (float('inf'), float('inf'), float('inf'))
		while low <= high:
			mid = (low + high) // 2
			first = arr[mid] - temp
			second = _sum - arr[mid]
			if abs(first - second) < diff:
				index = mid
				diff = abs(first - second)
			if first < second:
				low = mid + 1
			else:
				high = mid - 1
		return index


class Solution:

	def help(self, a):
		n = len(a)
		p = [0] * (n + 1)
		for i in range(n):
			p[i] = a[i]
			if i > 0:
				p[i] += p[i - 1]
		tmp = [[0, 0]]
		for i in range(1, n):
			(l, h) = (1, i)
			dif = 2e+18
			t = [0, 0]
			while l <= h:
				mid = (l + h) // 2
				x = p[mid - 1]
				y = p[i] - x
				if abs(x - y) < dif:
					dif = abs(x - y)
					t[0] = x
					t[1] = y
				if x > y:
					h = mid - 1
				else:
					l = mid + 1
			tmp.append(t)
		return tmp

	def reverse(self, a):
		n = len(a)
		for i in range(n // 2):
			(a[i], a[n - i - 1]) = (a[n - i - 1], a[i])

	def minDifference(self, N, A):
		ans = 2e+18
		x = self.help(A)
		self.reverse(A)
		y = self.help(A)
		y.reverse()
		for i in range(1, N - 2):
			ans = min(ans, max(max(x[i][0], x[i][1]), max(y[i + 1][0], y[i + 1][1])) - min(min(x[i][0], x[i][1]), min(y[i + 1][0], y[i + 1][1])))
		return ans


class Solution:

	def minDifference(self, N, A):

		def helper(lst, low, high):
			left = lst[low - 1] if low > 0 else 0
			localTot = lst[high] - left
			while low < high:
				mid = low + (high - low) // 2
				if lst[mid] - left < localTot // 2:
					low = mid + 1
				else:
					high = mid
			opt1 = lst[low] - left
			opt2 = localTot - opt1
			if low > 0:
				opt3 = lst[low - 1] - left
				opt4 = localTot - opt3
				if abs(opt2 - opt1) >= abs(opt4 - opt3):
					return [opt3, opt4]
			return [opt1, opt2]
		adj = []
		for i in range(N):
			if adj:
				adj.append(adj[-1] + A[i])
			else:
				adj.append(A[i])
		out = 10 ** 9
		for i in range(1, N - 2):
			left = helper(adj, 0, i)
			right = helper(adj, i + 1, N - 1)
			local = max(left[0], left[1], right[0], right[1]) - min(left[0], left[1], right[0], right[1])
			out = min(out, local)
		return out


import bisect, itertools

class Solution:

	def split(self, psums, start, stop, gap):
		target = (psums[start] + psums[stop]) // 2
		i = bisect.bisect_left(psums, target, start + gap, stop - gap)
		if i > start + gap and psums[i] - target > target - psums[i - 1]:
			i -= 1
		return i

	def minDifference(self, N, A):
		psums = [*itertools.accumulate(itertools.chain([0], A))]
		i2 = self.split(psums, 0, N, 2)
		i2min = max(i2 - 2, 2)
		i2max = min(i2 + 2, N - 2)
		min_diff = psums[N]
		for i2 in range(i2min, i2max + 1):
			i1 = self.split(psums, 0, i2, 1)
			i3 = self.split(psums, i2, N, 1)
			sums = (psums[i1], psums[i2] - psums[i1], psums[i3] - psums[i2], psums[N] - psums[i3])
			diff = max(sums) - min(sums)
			min_diff = min(diff, min_diff)
		return min_diff


class Solution:

	def binary(self, dp, start, end, k, temp):
		(mid, idx) = (-1, -1)
		diff = float('inf')
		while start <= end:
			mid = start + (end - start) // 2
			first = dp[mid] - temp
			second = k - dp[mid]
			if abs(first - second) < diff:
				idx = mid
				diff = abs(first - second)
			if first <= second:
				start = mid + 1
			else:
				end = mid - 1
		return idx

	def minDifference(self, N, A):
		if N == 4:
			return max(A) - min(A)
		dp = [0] * N
		dp[0] = A[0]
		for i in range(1, N):
			dp[i] = dp[i - 1] + A[i]
		(w, x, y, z) = (0, 0, 0, 0)
		ans = float('inf')
		for i in range(2, N - 1):
			idx = self.binary(dp, 0, i - 1, dp[i - 1], 0)
			w = dp[idx]
			x = dp[i - 1] - w
			idx = self.binary(dp, i, N - 1, dp[N - 1], dp[i - 1])
			y = dp[idx] - dp[i - 1]
			z = dp[N - 1] - dp[idx]
			ans = min(ans, max(x, y, w, z) - min(x, y, w, z))
		return ans


class Solution:

	def minDifference(self, N, A):
		sums = [0] * (N + 1)
		for (i, e) in enumerate(A):
			sums[i + 1] = sums[i] + e
		sumrange = lambda l, r: sums[r + 1] - sums[l]

		def search(l, r):
			goal = sumrange(l, r) // 2
			(lo, hi) = (l, r)
			while lo < hi:
				m = lo + (hi - lo) // 2
				if sumrange(l, m) < goal:
					lo = m + 1
				else:
					hi = m
			(v1, v2) = (sumrange(l, lo), sumrange(lo + 1, r))
			if lo > 0:
				(v3, v4) = (sumrange(l, lo - 1), sumrange(lo, r))
				if abs(v2 - v1) > abs(v4 - v3):
					return (v3, v4)
			return (v1, v2)
		ans = float('inf')
		for i in range(1, N - 2):
			(W, X) = search(0, i)
			(Y, Z) = search(i + 1, N - 1)
			vs = sorted((W, X, Y, Z))
			ans = min(ans, vs[3] - vs[0])
		return ans