You are given an array a and you need to generate an array b. You are allowed to apply only one type of operation on the array a, any number of times. 
In one operation you can swap a_{i} with a_{i+1} only if a_{i}+a_{i+1} is even.
Array b thus generated by applying above operation any number of times, should be lexicographically the largest among all arrays that can be generated from array a.
Example 1:
Input:
N=3
a[]={1,3,5}
Output:
5,3,1
Explanation: [1,3,5],[1,5,3],[3,1,5],[3,5,1],
[5,1,3] and [5,3,1] are all possible
values of array b while the last one is 
lexicographically largest.
 
Example 2:
Input:
N=4
a[]={1,3,4,2}
Output:
b[]={3,1,4,2}
Explanation: [1,3,4,2],[1,3,2,4],[3,1,2,4] and 
[3,1,4,2] are all possible values of b among 
which the last one is lexicographically largest one.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function lexicographically Largest() which takes the array arr[], and its size N as input parameters and returns the array b.
 
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}
1<= arr[i] <= 10^{5}
Array may contain duplicate elements.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution():

    def lexicographicallyLargest(self, a, n):

        #your code here

Solutions:
class Solution:

	def lexicographicallyLargest(self, a, n):
		(i, j) = (0, 1)
		while i < n - 1 and j < n:
			if (a[i] + a[j]) % 2 == 0:
				j += 1
			else:
				a[i:j] = sorted(a[i:j], reverse=True)
				i = j
				j += 1
			if j == n:
				a[i:j] = sorted(a[i:j], reverse=True)
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		cur_elems = []
		result = []
		for elem in a:
			if not cur_elems or elem % 2 == cur_elems[-1] % 2:
				cur_elems.append(elem)
			else:
				cur_elems.sort(reverse=True)
				result.extend(cur_elems)
				cur_elems = [elem]
		cur_elems.sort(reverse=True)
		result.extend(cur_elems)
		return result


class Solution:

	def lexicographicallyLargest(self, a, n):
		i = 0
		while i < n:
			j = i + 1
			while j < n and (a[j] + a[j - 1]) % 2 == 0:
				j += 1
			l = a[i:j]
			l.sort(reverse=True)
			a[i:j] = l
			i = j
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		ans = []
		temp = []
		temp.append(a[0])
		for i in range(1, len(a)):
			if (a[i] + a[i - 1]) % 2 == 0:
				temp.append(a[i])
				continue
			temp.sort(reverse=True)
			ans += temp
			temp = []
			temp.append(a[i])
		temp.sort(reverse=True)
		ans = ans + temp
		return ans


class Solution:

	def lexicographicallyLargest(self, a, n):
		i = 0
		ans = []
		while i < n:
			j = i + 1
			while j < n and a[j] % 2 == a[j - 1] % 2:
				j += 1
			tmp = a[i:j]
			tmp.sort(reverse=True)
			ans.extend(tmp)
			i = j
		return ans


class Solution:

	def lexicographicallyLargest(self, a, n):
		i = 0
		while i < n:
			j = i + 1
			while j < n and (a[j] + a[j - 1]) % 2 == 0:
				j += 1
			a[i:j] = sorted(a[i:j])[::-1]
			i = j
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		chunk = 0
		oe = a[0] % 2
		tmp = [(chunk, a[0])]
		for i in a[1:]:
			if i % 2 != oe:
				chunk += 1
				oe = i % 2
			tmp.append((chunk, i))
		tmp.sort(key=lambda x: (x[0], -x[1]))
		return list(map(lambda x: x[1], tmp))


class Solution:

	def lexicographicallyLargest(self, a, n):
		l = [a[0]]
		for i in range(1, n):
			if (a[i - 1] + a[i]) % 2 == 0:
				l.append(a[i])
			else:
				l.sort(reverse=True)
				a[i - len(l):i] = l
				l = [a[i]]
		if len(l) != 1:
			l.sort(reverse=True)
			a[n - len(l):n] = l
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		s = 0
		for i in range(n - 1):
			if (a[i] + a[i + 1]) % 2 == 0:
				(a[i + 1], a[i]) = (a[i], a[i + 1])
			else:
				if i - s >= 1:
					a[s:i + 1] = sorted(a[s:i + 1], reverse=True)
				s = i + 1
		if s == 0:
			a.sort(reverse=True)
		elif n - s >= 1:
			a[s:] = sorted(a[s:], reverse=True)
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		ans = []
		cur = a[0]
		v = [cur]
		for i in range(1, n):
			if cur & 1 == a[i] & 1:
				v.append(a[i])
			else:
				for x in sorted(v, reverse=True):
					ans.append(x)
				cur = a[i]
				v = [cur]
		for x in sorted(v, reverse=True):
			ans.append(x)
		return ans


class Solution:

	def lexicographicallyLargest(self, a, n):
		b = []
		small = []
		for i in range(n):
			if not small:
				small.append(a[i])
			elif not (small[-1] + a[i]) % 2:
				small.append(a[i])
			else:
				small.sort()
				while small:
					b.append(small.pop())
				small.append(a[i])
		if small:
			small.sort()
			while small:
				b.append(small.pop())
		return b


class Solution:

	def lexicographicallyLargest(self, a, n):
		swapBoundaries = {}
		prev = None
		bound = []
		i = 0
		for num in a:
			if prev is None:
				bound.append(num)
				prev = num % 2
			elif prev == num % 2:
				bound.append(num)
			else:
				swapBoundaries[i] = bound
				i += 1
				bound = [num]
				prev = num % 2
		if bound:
			swapBoundaries[i] = bound
			i += 1
		array = []
		for x in range(i):
			array += sorted(swapBoundaries[x], reverse=True)
		return array


class Solution:

	def lexicographicallyLargest(self, l, n):
		st = 0
		end = 0
		for i in range(n - 1):
			if (l[i] + l[i + 1]) % 2 == 0:
				end += 1
			else:
				l[st:end + 1] = sorted(l[st:end + 1], reverse=True)
				st = end + 1
				end = end + 1
		l[st:end + 1] = sorted(l[st:end + 1], reverse=True)
		return l


class Solution:

	def lexicographicallyLargest(self, a, n):
		(is_even, end) = (True, len(a) - 1)
		for i in range(len(a) - 1, -1, -1):
			if a[i] % 2 == 0:
				if is_even:
					if i != 0:
						continue
					else:
						self.quicksort(a, i, end)
						self.reverse_list(a, i, end)
				else:
					self.quicksort(a, i + 1, end)
					self.reverse_list(a, i + 1, end)
					(is_even, end) = (True, i)
			elif not is_even:
				if i != 0:
					continue
				else:
					self.quicksort(a, i, end)
					self.reverse_list(a, i, end)
			else:
				self.quicksort(a, i + 1, end)
				self.reverse_list(a, i + 1, end)
				(is_even, end) = (False, i)
		return a

	def reverse_list(self, array, beg, fin):
		if beg == fin:
			return
		else:
			while beg < fin:
				(array[beg], array[fin]) = (array[fin], array[beg])
				beg += 1
				fin -= 1
			return

	def quicksort(self, array, low, high):
		if low < high:
			ind = self.partition(array, low, high)
			self.quicksort(array, low, ind - 1)
			self.quicksort(array, ind + 1, high)
		return array

	def partition(self, arr, lo, hi):
		piv = arr[hi]
		(i, j) = (lo, hi - 1)
		while i < j:
			while arr[i] <= piv and i < hi:
				i += 1
			while arr[j] >= piv and j > lo:
				j -= 1
			if i < j:
				(arr[i], arr[j]) = (arr[j], arr[i])
		if arr[i] > piv:
			(arr[i], arr[hi]) = (arr[hi], arr[i])
		return i


class Solution:

	def lexicographicallyLargest(self, a, n):
		b = a[:]
		x = list(map(lambda y: y % 2, a))
		flag = x[0]
		p1 = 0
		p2 = 1
		for i in range(1, n):
			if x[i] == flag:
				p2 += 1
			else:
				b[p1:p2] = sorted(b[p1:p2])[::-1]
				flag = x[i]
				p1 = i
				p2 = i + 1
		b[p1:p2] = sorted(b[p1:p2])[::-1]
		return b


class Solution:

	def lexicographicallyLargest(self, a, n):
		j = 0
		for i in range(1, n):
			if a[i - 1] % 2 == a[i] % 2:
				continue
			else:
				b = a[j:i]
				b.sort(reverse=True)
				a[j:i] = b
				j = i
		if j < n:
			b = a[j:n]
			b.sort(reverse=True)
			a[j:n] = b
		return a


from typing import List

class Solution:

	def lexicographicallyLargest(self, a, n):
		i = 0
		while i < n:
			j = i + 1
			while j < n and (a[j] % 2 + a[j - 1]) % 2 == 0:
				j += 1
			a[i:j] = sorted(a[i:j], reverse=True)
			i = j
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		oddeven = self.oddeve(a, n)
		result = a[:]
		for i in oddeven:
			result[i[0]:i[1]] = sorted(a[i[0]:i[1]], reverse=True)
		return result

	def oddeve(self, a, n):
		system = []
		i = 0
		while i < n - 1:
			oddeve = a[i] % 2
			j = i + 1
			while j < n and oddeve == a[j] % 2:
				j += 1
			if i != j - 1:
				system.append([i, j])
			i = j
		return system


class Solution:

	def lexicographicallyLargest(self, a, n):
		out = [a[0]]
		v = []
		for i in range(1, n):
			if out[-1] % 2 != a[i] % 2:
				out.sort(reverse=True)
				v.extend(out)
				out.clear()
				out.append(a[i])
			else:
				out.append(a[i])
		out.sort(reverse=True)
		v.extend(out)
		return v


class Solution:

	def lexicographicallyLargest(self, a, n):
		b = []
		i = 0
		while i < n:
			arr = []
			j = i
			while j < n and a[j] % 2 == a[i] % 2:
				arr.append(a[j])
				j += 1
			arr.sort(reverse=True)
			b.extend(arr)
			i = j
		return b


class Solution:

	def lexicographicallyLargest(self, a, n):
		ans = []
		i = 0
		while i < n:
			temp = []
			if a[i] % 2 == 0:
				while i < n and a[i] % 2 == 0:
					temp.append(a[i])
					i += 1
			else:
				while i < n and a[i] % 2 == 1:
					temp.append(a[i])
					i += 1
			temp.sort()
			ans.append(temp[::-1])
		res = []
		for i in ans:
			for j in i:
				res.append(j)
		return res


class Solution:

	def lexicographicallyLargest(self, a, n):
		i = 0
		(temp, res) = ([], [])
		while i < n:
			while i < n and a[i] % 2 == 0:
				res.append(a[i])
				i += 1
			if len(res) > 0:
				res.sort(reverse=True)
				temp += res
				res = []
			while i < n and a[i] % 2 != 0:
				res.append(a[i])
				i += 1
			if len(res) > 0:
				res.sort(reverse=True)
				temp += res
				res = []
		return temp


class Solution:

	def lexicographicallyLargest(self, a, n):
		k = 0
		i = 0
		while i < n - 1:
			if (a[i] + a[i + 1]) % 2 != 0:
				b = a[k:i + 1]
				b.sort(reverse=True)
				a[k:i + 1] = b
				k = i + 1
			elif (a[i] + a[i + 1]) % 2 == 0 and i == n - 2:
				b = a[k:i + 2]
				b.sort(reverse=True)
				a[k:i + 2] = b
				break
			i += 1
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		start = 0
		end = 1
		while start < n and end < n:
			if (a[start] + a[end]) % 2 == 0:
				end += 1
			else:
				a[start:end] = sorted(a[start:end], reverse=True)
				start = end
				end += 1
		if end == n:
			a[start:end] = sorted(a[start:end], reverse=True)
		return a


import heapq

class Solution:

	def lexicographicallyLargest(self, a, n):
		i = 0
		b = []
		while i < n:
			j = i + 1
			while j < n and (a[j] % 2 == 0 and a[j - 1] % 2 == 0 or (a[j] % 2 == 1 and a[j - 1] % 2 == 1)):
				j += 1
			b += sorted(a[i:j])[::-1]
			i = j
		return b


class Solution:

	def lexicographicallyLargest(self, a, n):
		(prev, curr) = (a[0] % 2, 0)
		for (index, i) in enumerate(a):
			if i % 2 == prev:
				curr += 1
			else:
				a[index - curr:index] = sorted(a[index - curr:index], reverse=True)
				(curr, prev) = (1, i % 2)
		a[n - curr:] = sorted(a[n - curr:], reverse=True)
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		x = a[0] % 2
		st = 0
		for i in range(1, n):
			if a[i] % 2 != x:
				a[st:i] = sorted(a[st:i], reverse=True)
				st = i
				x = a[i] % 2
		a[st:n] = sorted(a[st:n], reverse=True)
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		if a[0] % 2 == 0:
			prev = 1
		else:
			prev = 0
		k = []
		k.append(a[0])
		res = []
		for i in a[1:]:
			if i % 2 == 0 and prev == 1:
				k.append(i)
			elif i % 2 == 0 and prev == 0:
				res.extend(sorted(k)[::-1])
				k = []
				k.append(i)
				prev = 1
			elif i % 2 != 0 and prev == 0:
				k.append(i)
			else:
				res.extend(sorted(k)[::-1])
				k = []
				k.append(i)
				prev = 0
		res.extend(sorted(k)[::-1])
		return res


class Solution:

	def lexicographicallyLargest(self, a, n):
		b = []
		accept = 'none'
		t = []
		for i in a:
			if i % 2 == 0:
				if accept == 'none':
					t.append(i)
					accept = 'even'
				elif accept == 'even':
					t.append(i)
				else:
					b += sorted(t, reverse=True)
					t = []
					t.append(i)
					accept = 'even'
			elif accept == 'none':
				t.append(i)
				accept = 'odd'
			elif accept == 'odd':
				t.append(i)
			else:
				b += sorted(t, reverse=True)
				t = []
				t.append(i)
				accept = 'odd'
		b += sorted(t, reverse=True)
		return b


import numpy as np

class Solution:

	def lexicographicallyLargest(self, arr, n):
		b = []
		small = []
		for i in range(n):
			if not small:
				small.append(a[i])
			elif not (small[-1] + a[i]) % 2:
				small.append(a[i])
			else:
				small.sort()
				while small:
					b.append(small.pop())
				small.append(a[i])
		if small:
			small.sort()
			while small:
				b.append(small.pop())
		return b


class Solution:

	def lexicographicallyLargest(self, a, n):
		ans = []
		t = []
		for i in a:
			if not t:
				t.append(i)
			elif t[-1] % 2 == i % 2:
				t.append(i)
			else:
				ans.append(t)
				t = [i]
		if t:
			ans.append(t)
		n = len(ans)
		for i in range(n):
			ans[i].sort(reverse=True)
		res = []
		for i in ans:
			res.extend(i)
		return res


class Solution:

	def lexicographicallyLargest(self, a, n):
		temp = []
		flag = False
		(st, en) = (0, 0)
		for i in range(n):
			if a[i] % 2 == 0:
				if not flag and temp:
					a[st:i] = sorted(temp, reverse=True)
					temp = []
				if not flag:
					st = i
				flag = True
				temp.append(a[i])
			else:
				if flag and temp:
					a[st:i] = sorted(temp, reverse=True)
					temp = []
				if flag:
					st = i
				flag = False
				temp.append(a[i])
		if temp:
			a[st:] = sorted(temp, reverse=True)
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		e = a[0] % 2
		s = 0
		for (i, j) in enumerate(a):
			if not j % 2 == e:
				a[s:i] = sorted(a[s:i], reverse=True)
				e = j % 2
				s = i
		a[s:n] = sorted(a[s:n], reverse=True)
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		i = 0
		ans = []
		while i < n:
			t = [a[i]]
			i += 1
			while i < n:
				if t[-1] % 2 == 0 and a[i] % 2 == 0:
					t.append(a[i])
				elif t[-1] % 2 and a[i] % 2:
					t.append(a[i])
				else:
					break
				i += 1
			if len(t) > 1:
				ans += sorted(t, reverse=True)
			else:
				ans.append(t[0])
		return ans


class Solution:

	def lexicographicallyLargest(self, a, n):
		is_even = a[0] % 2
		start = 0
		for (i, num) in enumerate(a):
			if not num % 2 == is_even:
				a[start:i] = sorted(a[start:i], reverse=True)
				is_even = num % 2
				start = i
		a[start:n] = sorted(a[start:n], reverse=True)
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		pr = 0
		i = 1
		while i < n:
			if a[i] % 2 != a[i - 1] % 2:
				a[pr:i] = sorted(a[pr:i], reverse=True)
				pr = i
			i += 1
		a[pr:i] = sorted(a[pr:i], reverse=True)
		return a


import numpy as np

class Solution:

	def lexicographicallyLargest(self, a, n):
		arr = np.array(a)
		i = 0
		while i < n:
			j = i + 1
			while j < n and arr[j - 1] % 2 == arr[j] % 2:
				j += 1
			arr[i:j].sort()
			arr[i:j] = arr[i:j][::-1]
			i = j
		a = arr.tolist()
		return a


class Solution:

	def lexicographicallyLargest(self, a, n):
		ans = []
		last = 0
		for i in range(n - 1):
			if (a[i] + a[i + 1]) % 2 == 1:
				ans.extend(sorted(a[last:i + 1], reverse=True))
				last = i + 1
		ans.extend(sorted(a[last:], reverse=True))
		return ans