Given an array A[] of N positive integers and two positive integers K_{1} and K_{2}. Find the sum of all elements between K_{1}^{th} and K_{2}^{th} smallest elements of the array. It may be assumed that (1 <= k1 < k2 <= n).
 
Example 1:
Input:
N  = 7
A[] = {20, 8, 22, 4, 12, 10, 14}
K1 = 3, K2 = 6
Output:
26
Explanation:
3rd smallest element is 10
6th smallest element is 20
Element between 10 and 20 
12,14. Their sum = 26.
 
Example 2:
Input
N = 6
A[] = {10, 2, 50, 12, 48, 13}
K1= 2, K2 = 6
Output:
73
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sumBetweenTwoKth() which takes the array A[], its size N and two integers K1 and K2 as inputs and returns the sum of all the elements between K_{1}^{th} and K_{2}^{th} smallest elements.
 
Expected Time Complexity: O(N. log(N))
Expected Auxiliary Space: O(N)
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ K_{1}, K_{2} ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def sumBetweenTwoKth(self, A, N, K1, K2):

        # Your code goes here

Solutions:
class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		d = [x for x in A if x > A[K1 - 1] and x < A[K2 - 1]]
		return sum(d)


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, k1, k2):
		x = []
		y = []
		heapq.heapify(x)
		heapq.heapify(y)
		for i in range(N):
			heapq.heappush(x, -A[i])
			heapq.heappush(y, -A[i])
			if len(x) > k1:
				heapq.heappop(x)
			if len(y) > k2:
				heapq.heappop(y)
		a1 = -heapq.heappop(x)
		a2 = -heapq.heappop(y)
		if a2 > a1:
			(a1, a2) = (a2, a1)
		c = 0
		for i in range(N):
			if A[i] < a1 and A[i] > a2:
				c += A[i]
		return c


import heapq as h

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		maxheap = []
		k1small = 0
		k2small = 0
		summ = 0
		for i in range(0, N):
			if len(maxheap) < K1:
				h.heappush(maxheap, -A[i])
			elif A[i] < -maxheap[0]:
				h.heappop(maxheap)
				h.heappush(maxheap, -A[i])
		k1small = -maxheap[0]
		maxheap = []
		for i in range(0, N):
			if len(maxheap) < K2:
				h.heappush(maxheap, -A[i])
			elif A[i] < -maxheap[0]:
				h.heappop(maxheap)
				h.heappush(maxheap, -A[i])
		k2small = -maxheap[0]
		if k1small > k2small:
			(k1small, k2small) = (k2small, k1small)
		for i in range(0, N):
			if A[i] > k1small and A[i] < k2small:
				summ = summ + A[i]
		return summ


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		l = A[K1:K2 - 1]
		return sum(l)


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):

		def findKthSmallest(arr, k):
			max_heap = []
			for i in arr:
				heapq.heappush(max_heap, -1 * i)
				if len(max_heap) > k:
					heapq.heappop(max_heap)
			return -1 * heapq.heappop(max_heap)
		min_val = findKthSmallest(A, K1)
		max_val = findKthSmallest(A, K2)
		res = 0
		for ele in A:
			if ele > min_val and ele < max_val:
				res += ele
		return res


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A = sorted(A)
		s = sum(A[K1:K2 - 1])
		return s


def suma(x):
	a = len(x)
	s = 0
	for i in range(a):
		s += x[i]
	return s

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		a = suma(A[K1:])
		b = suma(A[K2 - 1:])
		return a - b


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		new = A[K1 - 1:K2 - 1]
		return sum(new) - new[0]


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		a = []
		s = 0
		for i in range(K1, K2 - 1):
			a.append(A[i])
		for i in a:
			s += i
		return s


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		sum = 0
		for i in range(K1, K2 - 1):
			sum += A[i]
		return sum


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		ans = []
		heapq.heapify(ans)
		for i in range(N):
			heapq.heappush(ans, -1 * A[i])
			if len(ans) >= K2:
				heapq.heappop(ans)
		sm = 0
		while len(ans) > K1:
			sm += heapq.heappop(ans) * -1
		return sm


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):

		def get_ele(arr, k):
			import heapq
			heap = []
			for i in range(0, len(arr)):
				heapq.heappush(heap, -arr[i])
				if len(heap) > k:
					heapq.heappop(heap)
			return -heap[0]
		y = get_ele(A, K1)
		x = get_ele(A, K2)
		summ = 0
		for i in range(0, N):
			if A[i] > y and A[i] < x:
				summ += A[i]
		return summ


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		sumi = 0
		for i in range(N):
			if i > K1 - 1 and i < K2 - 1:
				sumi += A[i]
		return sumi


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		sm = 0
		x1 = self.min_values(A, N, K1)
		x2 = self.min_values(A, N, K2)
		for i in range(N):
			if x1 < A[i] < x2:
				sm += A[i]
		return sm

	def min_values(self, A, N, K):
		minh = []
		heapq.heapify(minh)
		for i in range(N):
			heapq.heappush(minh, A[i] * -1)
			if len(minh) > K:
				heapq.heappop(minh)
		return minh[0] * -1


import heapq

class Solution:

	def sumBetweenTwoKth(self, arr, n, k1, k2):
		heapq.heapify(arr)
		l = arr.copy()
		s1 = 0
		s2 = 0
		for i in range(0, k1):
			s1 += heapq.heappop(l)
		l = arr.copy()
		for i in range(1, k2):
			s2 += heapq.heappop(l)
		total_sum = s2 - s1
		return total_sum


import heapq

class Solution:

	def sumBetweenTwoKth(self, arr, N, K1, K2):
		heapq.heapify(arr)
		l = arr.copy()
		s1 = 0
		s2 = 0
		for i in range(0, K1):
			s1 += heapq.heappop(l)
		l = arr.copy()
		for i in range(1, K2):
			s2 += heapq.heappop(l)
		s3 = s2 - s1
		return s3


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		res = sorted(A)
		l = []
		ind1 = res.index(res[K1 - 1])
		ind2 = res.index(res[K2 - 1])
		for i in range(ind1 + 1, ind2):
			l.append(res[i])
		return sum(l)


import sys
from heapq import *

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		heap1 = [-sys.maxsize] * K1
		heap2 = [-sys.maxsize] * K2
		heapify(heap1)
		heapify(heap2)
		for num in A:
			if num < -heap1[0]:
				heappop(heap1)
				heappush(heap1, -num)
			if num < -heap2[0]:
				heappop(heap2)
				heappush(heap2, -num)
		heappop(heap2)
		ans = -sum(heap2) - -sum(heap1)
		return ans


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		c = A[K1 - 1]
		d = A[K2 - 1]
		lst = []
		for i in range(N):
			if A[i] > c and A[i] < d:
				lst.append(A[i])
		ans = sum(lst)
		return ans


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		m = A[K1 - 1]
		n = A[K2 - 1]
		s = 0
		for i in A:
			if i > m and i < n:
				s = s + i
		return s


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		lst = []
		for i in A:
			if i > A[K1 - 1] and i < A[K2 - 1]:
				lst.append(i)
		s = sum(lst)
		return s


import heapq

class Solution:

	def sumBetweenTwoKth(self, array, N, k1, k2):

		def findKthLargest(k):
			heap = []
			for num in array:
				if len(heap) < k:
					heapq.heappush(heap, -1 * num)
				elif -num > heap[0]:
					heapq.heappop(heap)
					heapq.heappush(heap, -1 * num)
			return heap[0] * -1
		num1 = findKthLargest(k1)
		num2 = findKthLargest(k2)
		ans = 0
		for num in array:
			if num > num1 and num < num2:
				ans += num
		return ans


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		i = A[K1 - 1]
		j = A[K2 - 1]
		sum = 0
		for m in A:
			if m > i and m < j:
				sum = sum + m
		return sum


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):

		def kthSmallest(a, k):
			maxh = []
			for i in range(len(a)):
				heapq.heappush(maxh, -a[i])
				if len(maxh) > k:
					heapq.heappop(maxh)
			return -maxh[0]
		ax = kthSmallest(A, K1)
		by = kthSmallest(A, K2)
		ans = 0
		for i in range(N):
			if A[i] > ax and A[i] < by:
				ans += A[i]
		return ans


from heapq import heapify, heappush, heappop

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		sum = 0
		new = [-1 * x for x in A]
		heapify(new)
		while N > K2 - 1:
			heappop(new)
			N -= 1
		while N > K1:
			sum += -1 * heappop(new)
			N -= 1
		return sum


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, k1, k2):
		heapq.heapify(A)
		for i in range(k1):
			heapq.heappop(A)
		i = k1
		sum = 0
		while i < k2 - 1:
			sum += heapq.heappop(A)
			i += 1
		return sum


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		heap = []
		heapq.heapify(heap)
		for i in range(len(A)):
			heapq.heappush(heap, A[i])
		k1 = K1
		k2 = K2
		while k1:
			heapq.heappop(heap)
			k1 -= 1
		ans = 0
		k = k2 - K1 - 1
		while k > 0:
			if heap:
				ele = heapq.heappop(heap)
				ans += ele
			k -= 1
		return ans


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		arr = set(A)
		arr = sorted(A)
		sum = 0
		for i in range(K1, K2 - 1):
			sum = sum + arr[i]
		return sum


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		s = 0
		for i in range(N):
			if i > K1 - 1:
				s += A[i]
			if i == K2 - 1:
				s -= A[i]
				break
		return s


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		if K1 >= N:
			return 0
		A.sort()
		if K2 <= N:
			sum1 = 0
			for i in range(K1, K2 - 1):
				sum1 = sum1 + A[i]
		else:
			sum1 = 0
			for i in range(K1, N):
				sum1 = sum1 + A[i]
		return sum1


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		if K1 > N or K2 > N:
			return 0
		m = max(K1, K2)
		heap = []
		for i in A:
			heapq.heappush(heap, i)
		(ans, x) = (0, 0)
		while heap:
			e = heapq.heappop(heap)
			x += 1
			if x > K1 and x < K2:
				ans += e
		return ans


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		tot_sum = 0

		def kthElement(A, k, N):
			import heapq
			A = [-1 * n for n in A]
			hp = A[:k]
			heapq.heapify(hp)
			for i in range(k, N):
				heapq.heappushpop(hp, A[i])
			return -1 * hp[0]
		k1num = kthElement(A, K1, N)
		k2num = kthElement(A, K2, N)
		for i in range(0, N):
			if A[i] > k1num and A[i] < k2num:
				tot_sum += A[i]
		return tot_sum


import heapq

class Solution:

	def kthSmallest(self, arr, l, r, k):
		myList = []
		heapq.heapify(myList)
		for i in range(l, r + 1):
			heapq.heappush(myList, arr[i] * -1)
			if len(myList) > k:
				heapq.heappop(myList)
		return myList[0] * -1

	def sumBetweenTwoKth(self, A, N, K1, K2):
		n1 = self.kthSmallest(A, 0, N - 1, K1)
		n2 = self.kthSmallest(A, 0, N - 1, K2)
		sum = 0
		for i in range(N):
			if n1 < A[i] < n2:
				sum += A[i]
		return sum


from heapq import heappop, heappush, heapify

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):

		def fun(A, K):
			maxheap = []
			heapify(maxheap)
			for i in A:
				heappush(maxheap, -i)
				if len(maxheap) > K:
					heappop(maxheap)
			return -1 * heappop(maxheap)
		max1 = fun(A, K1)
		max2 = fun(A, K2)
		ans = 0
		for i in A:
			if i > max1 and i < max2:
				ans += i
		return ans


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		from heapq import heapify, heappop, heappush

		def fun(A, K):
			h = []
			heapify(h)
			for i in A:
				heappush(h, -i)
				if len(h) > K:
					heappop(h)
			return -1 * heappop(h)
		r1 = fun(A, K1)
		r2 = fun(A, K2)
		ans = 0
		for i in A:
			if i > r1 and i < r2:
				ans += i
		return ans


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		s = 0
		while K1 < K2 - 1:
			s += A[K1]
			K1 = K1 + 1
		return s


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		num1 = kthSmallest(K1, A)
		num2 = kthSmallest(K2, A)
		res = 0
		for num in A:
			if num > num1 and num < num2:
				res += num
		return res

def kthSmallest(k, arr):
	pq = []
	for num in arr:
		heapq.heappush(pq, -num)
		if len(pq) > k:
			heapq.heappop(pq)
	return -heapq.heappop(pq)


class Solution:

	def sumBetweenTwoKth(self, a, N, K1, K2):
		a.sort()
		return sum(a[K1:K2 - 1])


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		p = sorted(A)
		u = K1 - 1
		v = K2 - 1
		a = p[u + 1:v]
		return sum(a)


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		heap = []
		heapq.heapify(heap)
		for i in range(N):
			heapq.heappush(heap, -1 * A[i])
			if len(heap) > K2:
				heapq.heappop(heap)
		second = -1 * heap[0]
		while len(heap) > K1:
			heapq.heappop(heap)
		first = -1 * heap[0]
		total = 0
		for i in range(N):
			if A[i] > first and A[i] < second:
				total += A[i]
		return total


from heapq import *

class Solution:

	def sumBetweenTwoKth(self, arr, n, k1, k2):
		maxHeap = []
		for i in range(n):
			if i < k2 - 1:
				heappush(maxHeap, -arr[i])
			elif maxHeap[0] < -arr[i]:
				heappop(maxHeap)
				heappush(maxHeap, -arr[i])
		summ = 0
		for i in range(k2 - k1 - 1):
			summ += -heappop(maxHeap)
		return summ


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		x = A[K1 - 1]
		y = A[K2 - 1]
		s = 0
		for i in A:
			if i > x and i < y:
				s += i
		return s


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		heapq.heapify(A)
		total = 0
		while K1 > 0 or K2 > 0:
			el = heapq.heappop(A)
			K1 -= 1
			K2 -= 1
			if K1 < 0 and K2 > 0:
				total += el
		return total


class Solution:

	def sumBetweenTwoKth(self, A, N, k1, k2):
		t = sorted(A)
		s = 0
		f = 0
		return sum(t[k1:k2 - 1])


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		import heapq
		l = []
		l1 = []
		heapq.heapify(A)
		for i in range(N):
			a = heapq.heappop(A)
			l.append(a)
		for i in range(K1, K2 - 1):
			l1.append(l[i])
		return sum(l1)


from heapq import *

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		minheap = [num for num in A]
		heapify(minheap)
		(numK1, numK2) = (None, None)
		for i in range(K2):
			x = heappop(minheap)
			if i + 1 == K1:
				numK1 = x
			elif i + 1 == K2:
				numK2 = x
				break
		res = 0
		for num in A:
			if num > numK1 and num < numK2:
				res += num
		return res


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		list1 = []
		list1 = list1 + A
		list1.sort()
		ele1 = list1[K1 - 1]
		ele3 = list1[K2 - 1]
		r1 = max(ele1, ele3)
		r3 = min(ele1, ele3)
		s = 0
		for i in range(0, len(A)):
			if A[i] > r3 and A[i] < r1:
				s = s + A[i]
		return s


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		heap = []
		for i in A:
			heapq.heappush(heap, i)
		count = 0
		sum_ = 0
		while heap:
			p = heapq.heappop(heap)
			count += 1
			if count > K1 and count < K2:
				sum_ += p
			elif count >= K2:
				break
		return sum_


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):

		def ksmallest(A, x):
			heap = []
			for ch in A:
				heapq.heappush(heap, -ch)
				if len(heap) > x:
					heapq.heappop(heap)
			return -heap[0]
		first = ksmallest(A, K1)
		second = ksmallest(A, K2)
		summ = 0
		for ch in A:
			if second > ch > first:
				summ += ch
		return summ


from heapq import *

class Solution:

	def kthSmallest(self, arr, k):
		heap = []
		heapify(heap)
		for num in arr:
			heappush(heap, -1 * num)
			if len(heap) == k + 1:
				heappop(heap)
		return -1 * heappop(heap)

	def sumBetweenTwoKth(self, A, N, K1, K2):
		k1thSmallest = self.kthSmallest(A, K1)
		k2thSmallest = self.kthSmallest(A, K2)
		sum = 0
		for num in A:
			if num > k1thSmallest and num < k2thSmallest:
				sum += num
		return sum


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		sum1 = 0
		A.sort()
		min1 = A[K1 - 1]
		max1 = A[K2 - 1]
		for i in A:
			if i > min1 and i < max1:
				sum1 += i
		return sum1


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		sum = 0
		A.sort()
		p = A[K1 - 1]
		q = A[K2 - 1]
		for i in A:
			if p < i < q:
				sum += i
		return sum


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		A.sort()
		ele1 = A[K1 - 1]
		ele2 = A[K2 - 1]
		sum1 = 0
		for i in range(len(A)):
			if A[i] > ele1 and A[i] < ele2:
				sum1 += A[i]
		return sum1


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		a = sorted(A)
		b = a[K1 - 1]
		c = a[K2 - 1]
		s = 0
		for i in a:
			if i > b and i < c:
				s = s + i
		return s


class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		a = sorted(A)
		a = [i for i in a]
		return sum(a[K1:K2 - 1])


import heapq

class Solution:

	def sumBetweenTwoKth(self, A, N, K1, K2):
		ans = 0
		heapq.heapify(A)
		for i in range(K1):
			heapq.heappop(A)
		for i in range(K2 - K1 - 1):
			ans += heapq.heappop(A)
		return ans


from heapq import *

class Solution:

	def sumBetweenTwoKth(self, arr, n, k1, k2):
		heap = []
		for item in arr:
			heappush(heap, item)
		for _ in range(k1):
			heappop(heap)
		result = 0
		for _ in range(k2 - k1 - 1):
			result += heappop(heap)
		return result