You are given a sorted array a of length n. For each i(0<=i<=n-1), you have to make all the elements of the array from index 0 till i equal, using minimum number of operations. In one operation you either increase or decrease the array element by 1.
You have to return a list which contains the minimum number of operations for each i, to accomplish the above task.
Note:
1. 0-based indexing.
2. For each index, you need to consider the same array which was given to you at the start.
Example 1:
Input:
N=4
A={1,6,9,12}
Output:
0 5 8 14
Explanation:
For i=0, We do not need to perform any 
operation, our array will be {1}->{1}.
And minimum number of operations
will be 0.
For i=1, We can choose to convert all 
the elements from 0<=j<=i to 4, our 
array will become {1,6}->{4,4}. And 
minimum number of operations will be 
|1-4|+|6-4|=5.
For i=2, We can choose to convert all 
the elements from 0<=j<=i to 6, our 
array will become {1,6,9}->{6,6,6} and 
the minimum number of operations will 
be |1-6|+|6-6|+|9-6|=8.
Similarly, for i=3, we can choose to 
convert all the elements to 8, 
{1,6,9,12}->{8,8,8,8}, and the 
minimum number of operations will be 14.
Example 2:
Input:
N=7
A={1,1,1,7,7,10,19}
Output:
0 0 0 6 12 21 33
Explanation:
Possible operations could be:
{1}->{1}
{1,1}->{1,1}
{1,1,1}->{1,1,1}
{1,1,1,7}->{1,1,1,1}
{1,1,1,7,7}->{1,1,1,1,1}
{1,1,1,7,7,10}->{5,5,5,5,5,5}
{1,1,1,7,7,10,19}->{7,7,7,7,7,7,7}
Your Task:
You don't need to read input or print anything. Your task is to complete the function optimalArray() which takes N(length of array) and  an array A as input and returns an array of size N  with optimal answer for each index i.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{6}
-10^{5} <= A[i] <= 10^{5}
Sum of N over all test case does not exceed 10^{6}.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: from typing import List





class Solution:

    def optimalArray(self, n : int, a : List[int]) -> List[int]:

        # code here

        



Solutions:
from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		res = [0 for _ in range(n)]
		ind = 1
		for i in range(1, n):
			res[ind] = res[i - 1] + (a[i] - a[i // 2])
			ind += 1
		return res


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		ans = [0] * n
		for i in range(1, n):
			ans[i] = ans[i - 1] + a[i] - a[i // 2]
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		r = [0]
		for i in range(1, n):
			c = r[i - 1] + a[i] - a[i // 2]
			r.append(c)
		return r


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		ans = []
		c = 0
		for i in range(n):
			m = i // 2
			ans.append(c + (a[i] - a[m]))
			c = ans[i]
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		currAns = 0
		res = []
		for i in range(n):
			currAns += a[i] - a[i // 2]
			res.append(currAns)
		return res


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		out = [0 for _ in range(n)]
		for i in range(1, len(a)):
			out[i] = out[i - 1] + a[i] - a[i // 2]
		return out


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		leftsum = 0
		rightsum = 0
		ans = [0]
		for i in range(1, n):
			if i % 2 != 0:
				leftsum += a[(i - 1) // 2]
				rightsum += a[i]
			else:
				rightsum += a[i] - a[i // 2]
			ans.append(rightsum - leftsum)
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		smedian = 0
		stotal = 0
		ans = []
		for i in range(n):
			stotal += a[i]
			if (i + 1) % 2 != 0:
				median = a[i // 2]
				smedian = smedian + a[i // 2]
				ans.append(abs(smedian - (i // 2 + 1) * median) + abs(stotal - smedian - i // 2 * median))
			else:
				median = (a[i // 2] + a[(i + 1) // 2]) // 2
				ans.append(abs(smedian - (i // 2 + 1) * median) + abs(stotal - smedian - (i // 2 + 1) * median))
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, arr: List[int]) -> List[int]:
		ans = []
		prefix = [0] * n
		prefix[0] = arr[0]
		ans.append(0)
		for i in range(1, n):
			prefix[i] += prefix[i - 1] + arr[i]
			curr = 0
			if i % 2 == 0:
				j = i // 2
				sum1 = prefix[j - 1]
				sum2 = prefix[i] - prefix[j]
				curr = sum2 - sum1
			else:
				j = i // 2
				sum1 = prefix[j]
				sum2 = prefix[i] - prefix[j]
				curr = sum2 - sum1
			ans.append(curr)
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		sum1 = 0
		sum2 = 0
		ans = []
		mid = (n + 1) // 2
		for i in range(mid):
			sum1 += a[i]
			if 2 * i < n:
				sum2 += a[2 * i]
				diff = (i + 1) * a[i] - sum1 + (sum2 - sum1 - i * a[i])
				ans.append(diff)
			if 2 * i + 1 < n:
				sum2 += a[2 * i + 1]
				diff = (i + 1) * a[i] - sum1 + (sum2 - sum1 - (i + 1) * a[i])
				if diff < 0:
					diff = diff * -1
				ans.append(diff)
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		ans = [0] * n
		last_median = 1
		s1 = s2 = 0
		for i in range(1, n):
			if (i + 1) % 2 == 0:
				s1 += a[i // 2]
				s2 += a[i]
			else:
				s2 += a[i] - a[i // 2]
			ans[i] = s2 - s1
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		c = 0
		x = a[0]
		r = [0]
		k = 0
		p = a[0]
		odd = a[0]
		even = a[0]
		if n == 1:
			return r
		codd = abs(a[0] - a[1])
		ceven = abs(a[1] - a[0])
		if n == 2:
			r.append(abs(a[0] - a[1]))
			return r
		r.append(abs(a[0] - a[1]))
		for i in range(2, n):
			n1 = i + 1
			k = int(n1 / 2)
			x = a[k]
			if n1 % 2 == 0:
				x1 = a[k - 1]
				codd = codd + abs(a[i] - x1)
				d = abs(a[k] - x)
				ceven = codd - d + k * d
				c = min(codd, ceven)
			else:
				codd = codd + abs(a[i] - x)
				c = codd
			r.append(c)
		return r

def find(l, n):
	k = int(n / 2)
	c = 0
	x = l[k]
	for i in range(n):
		c = c + abs(x - l[i])
	m = c
	if n % 2 == 0:
		x = l[k - 1]
		c1 = 0
		for i in range(n):
			c1 = c1 + abs(x - l[i])
		m = min(c, c1)
	return m


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		ans = []
		sm = 0
		pref = []
		for i in range(n):
			sm += a[i]
			pref.append(sm)
		for (i, num) in enumerate(a):
			mind = (i + 1) // 2
			md = a[mind]
			cur = (mind + 1) * md - pref[mind]
			if mind < i:
				cur += pref[i] - pref[mind] - (i - mind) * md
			ans.append(cur)
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, A: List[int]) -> List[int]:
		ans = []
		prefix = [0]
		for i in A:
			prefix.append(prefix[-1] + i)
		for i in range(n):
			if i % 2 == 0:
				ans.append(-prefix[(i + 2) // 2 - 1] + prefix[i + 1] - prefix[(i + 2) // 2])
			else:
				ans.append(prefix[i + 1] - 2 * prefix[(i + 1) // 2])
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		ans = []
		ans.append(0)
		summ = [0] * n
		summ[0] = a[0]
		for i in range(1, n):
			summ[i] = summ[i - 1] + a[i]
			ind = i // 2
			curr1 = summ[i] - summ[ind]
			if i % 2 == 0:
				curr2 = summ[ind - 1]
			else:
				curr2 = summ[ind]
			val = abs(curr1 - curr2)
			ans.append(val)
		return ans


from typing import List
from statistics import median

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		lis = []
		k = 0
		summ = 0
		oper = []
		for i in range(0, n):
			summ = summ + a[i]
			lis.append(summ)
			k += 1
			if k == 1:
				oper.append(0)
			elif k % 2 != 0:
				mid = int(k / 2)
				oper.append(lis[k - 1] - lis[mid] - lis[mid - 1])
			else:
				mid = int(k / 2)
				oper.append(lis[k - 1] - 2 * lis[mid - 1])
		return oper


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		ans = [0 for _ in range(n)]
		sum = 0
		for i in range(n):
			sum += a[i]
			midIdx = i // 2
			tgt = a[midIdx]
			ans[i] = ans[i - 1] + a[i] - tgt
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, arr: List[int]) -> List[int]:
		ans = [0]
		for i in range(1, len(arr)):
			m = ans[i - 1] + (arr[i] - arr[i // 2])
			ans.append(m)
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		r = []
		x = 0
		for i in range(len(a)):
			y = i // 2
			x += abs(a[y] - a[i])
			r.append(x)
		return r


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		l = [0]
		i = 0
		j = 1
		while len(l) != len(a):
			b = (j + i) // 2
			c = a[j] - a[b] + l[j - 1]
			l.append(c)
			j += 1
		return l


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		lout = [0]
		if n == 1:
			return lout
		pos = 1
		posMin = 0
		nextPos = 1
		while pos < n:
			opNum1 = lout[pos - 1] + a[pos] - a[posMin]
			if opNum1 == lout[pos - 1]:
				posMin += 1
				nextPos += 1
			else:
				if a[pos] == a[nextPos]:
					nextPos = pos
				opNum2 = lout[pos - 1] + a[pos] - a[nextPos] + (a[nextPos] - a[posMin]) * (2 * posMin - pos + 2)
				if opNum2 <= opNum1:
					opNum1 = opNum2
					posMin = nextPos
					nextPos += 1
					while nextPos < pos and a[nextPos] == a[nextPos + 1]:
						nextPos += 1
			lout.append(opNum1)
			pos += 1
		return lout


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		result = []
		diff = 0
		for i in range(0, n):
			mid = i // 2
			diff += a[i] - a[mid]
			result.append(diff)
		return result


from typing import List

class Solution:

	def optimalArray(self, n: int, arr: List[int]) -> List[int]:
		res = [0] * len(arr)
		front = back = 0
		for i in range(1, len(arr)):
			if i & 1:
				front += arr[i]
				back += arr[i // 2]
			else:
				front += arr[i] - arr[i // 2]
			res[i] = front - back
		return res


from typing import List

class Solution:

	def optimalArray(self, n: int, arr: List[int]) -> List[int]:
		res = [0] * len(arr)
		for i in range(1, len(arr)):
			cur = arr[i // 2]
			res[i] = res[i - 1] + abs(arr[i] - cur)
		return res


from typing import List

class Solution:

	def optimalArray(self, n: int, arr: List[int]) -> List[int]:
		ans = []
		tot = 0
		for i in range(n):
			ele = arr[i]
			medind = i // 2
			tot += arr[i] - arr[medind]
			ans.append(tot)
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, arr: List[int]) -> List[int]:
		(half, full) = (0, 0)
		res = []
		for i in range(n):
			full += arr[i]
			if i % 2:
				res.append(full - 2 * half)
			else:
				half += arr[i // 2]
				res.append(full - 2 * half + arr[i // 2])
		return res


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		res = []
		indx = 0
		res.append(0)
		for i in range(1, n):
			res.append(abs(res[i - 1] + (a[i] - a[i // 2])))
		return res


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		ans = []
		sum = [0 for i in range(n)]
		sum[0] = a[0]
		ans.append(0)
		for i in range(1, n):
			sum[i] = sum[i - 1] + a[i]
			cur = 0
			if i % 2 == 0:
				j = i // 2
				sum1 = sum[j - 1]
				sum2 = sum[i] - sum[j]
				cur = sum2 - sum1
			else:
				j = i // 2
				sum1 = sum[j]
				sum2 = sum[i] - sum[j]
				cur = sum2 - sum1
			ans.append(cur)
		return ans


from typing import List

class Solution:

	def optimalArray(self, n: int, a: List[int]) -> List[int]:
		p = [0]
		sum1 = 0
		sum2 = 0
		for i in range(1, n):
			if (i + 1) % 2 == 0:
				sum1 += a[i // 2]
				sum2 += a[i]
			else:
				sum2 += a[i] - a[i // 2]
			p.append(sum2 - sum1)
		return p