<jupyter_start><jupyter_text>Create the max number of `k` digits from an array of `n` digits where `k` <= `n`, while preserving the relative order of the digits<jupyter_code># naive sorting
# wrong solution as this does not preserve the order
def maxK(arr, k):
  return sorted(arr, reverse=True)[:k]

print(maxK([2,4,2,1], 2))
print(maxK([2,6,7,8], 2))
print(maxK([2,6,7,8], 4))
# heap
import heapq

# worst case complexity O(log(N)*N**2)
# when the array is sorted in ascending order and k == n
# the reason is because at each iteration, the code pops and discards k-1 elements from the heap
def maxK(arr, k):
  n = len(arr)
  pq = [(-v, idx) for idx, v in enumerate(arr)]
  heapq.heapify(pq)
  ans = []
  last = -1

  while k:
    tmp = []
    while pq and n-pq[0][1] < k:      
      tmp += heapq.heappop(pq),
  
    if pq:
      v, idx = heapq.heappop(pq)
      if idx > last:
        ans += -v,
        last = idx 
        k -= 1

    while tmp:
      heapq.heappush(pq, tmp.pop())
  return ans

print(maxK([2,4,2,1], 1))
print(maxK([2,4,2,1], 2))
print(maxK([2,4,2,1], 3))
print(maxK([2,4,2,1], 4))

print(maxK([2,6,7,8], 1))
print(maxK([2,6,7,8], 2))
print(maxK([2,6,7,8], 3))
print(maxK([2,6,7,8], 4))

print(maxK([1,2,3,4,5], 5))
# stack
# O(N)
def maxK(arr, k):
  stack = []
  n = len(arr)
  for idx, v in enumerate(arr):
    while n - idx + len(stack) > k and stack and stack[-1] < v:
      stack.pop()
    if len(stack) < k:
      stack += v,

  return stack

print(maxK([2,4,2,1], 1))
print(maxK([2,4,2,1], 2))
print(maxK([2,4,2,1], 3))
print(maxK([2,4,2,1], 4))

print(maxK([2,6,7,8], 1))
print(maxK([2,6,7,8], 2))
print(maxK([2,6,7,8], 3))
print(maxK([2,6,7,8], 4))

print(maxK([1,2,3,4,5], 5))<jupyter_output>[4]
[4, 2]
[4, 2, 1]
[2, 4, 2, 1]
[8]
[7, 8]
[6, 7, 8]
[2, 6, 7, 8]
[1, 2, 3, 4, 5]
{'fraction_non_alphanumeric': 0.21902654867256638, 'fraction_numerical': 0.07688053097345132, 'mean_word_length': 3.579746835443038, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '503177', 'license': 'Apache-2.0', 'n_tokens_mistral': 894, 'n_tokens_neox': 834, 'n_words': 220, 'path': 'Stack.ipynb', 'repo_name': 'lamnguyen2187/algorithms_collection', 'size': '1808'}