Array Quadruplet

[esthicodes]

Array Quadruplet

Given an unsorted array of integers arr and a number s, write a function findArrayQuadruplet that finds four numbers (quadruplet) in arr that sum up to s. Your function should return an array of these numbers in an ascending order. If such a quadruplet doesn’t exist, return an empty array.

Note that there may be more than one quadruplet in arr whose sum is s. You’re asked to return the first one you encounter (considering the results are sorted).

Explain and code the most efficient solution possible, and analyze its time and space complexities.

Example:

input: arr = [2, 7, 4, 0, 9, 5, 1, 3], s = 20

output: [0, 4, 7, 9] # The ordered quadruplet of (7, 4, 0, 9)
# whose sum is 20. Notice that there
# are two other quadruplets whose sum is 20:
# (7, 9, 1, 3) and (2, 4, 9, 5), but again you’re
# asked to return the just one quadruplet (in an
# ascending order)
Constraints:

[time limit] 5000ms

[input] array.integer arr

1 ≤ arr.length ≤ 100
[input] integer s

[output] array.integer

# esthi korea bs
# carla 

# target = s
def find_array_quadruplet(arr, s):
  n = len(arr)
  if n< 4:
    return []

  arr.sort()

  for i in range(n-3):

    if i != 0 and arr[i] == arr[i-1]:
      continue 

    for j in range(i+ 1, n-2):
      if j != 1 and arr[j] == arr [j-1]:
        continue 
      curr_sum = arr[i] + arr[ j]
      
      target_complement = s - curr_sum 

      low = j + 1 
      high = n -1 

      while low < high:
        curr_complement = arr[low] + arr[high]

        if curr_complement > target_complement :
          high -= 1 
        elif curr_complement < target_complement :

          low += 1 
        else:
          return [arr[i], arr[j], arr[low], arr[high]]

  return []

print(find_array_quadruplet([2, 7, 4, 0, 9, 5, 1, 3], s = 20))

# arr = [2, 7, 4, 0, 9, 5, 1, 3], s = 20
#  [0, 4, 7, 9]

[esthicodes]

esthi korea bs

carla

target = s

def find_array_quadruplet(arr, s):
n = len(arr)
if n < 4:
return []

arr.sort() # O(nlog(n))

for i in range(n-3):

if i != 0 and arr[i] == arr[i-1]:
  continue 

for j in range(i+ 1, n-2):
  if j != 1 and arr[j] == arr [j-1]:
    continue 
  curr_sum = arr[i] + arr[ j]
  
  target_complement = s - curr_sum 

  low = j + 1 
  high = n -1 

  while low < high:
    curr_complement = arr[low] + arr[high]

    if curr_complement > target_complement :
      high -= 1 
    elif curr_complement < target_complement :

      low += 1 
    else:
      return [arr[i], arr[j], arr[low], arr[high]]

return []

print(find_array_quadruplet([2, 7, 4, 0, 9, 5, 1, 3], s = 20))

curr_sum + target_complement + curr_complement = 3 = constant

O(constant) = O(1) -> space complexity

O(n^3)

n * n * n

2 for loops in n-quadrat and one while loop

eine while loop

arr = [2, 7, 4, 0, 9, 5, 1, 3], s = 20

[0, 4, 7, 9]

runtime: time: O(n)

space complexity: O(1). zusätzlich speicherplatz verwenden

speicher eine platz.