https://www.acmicpc.net/problem/2295
initial
Since time limit was 1s, even though the input was 1000 i didnt know if we could solve it with n^2 time. But turns out we can. (some solved with n^3 lol but i dont think it works in interviews).
My initial thought was it is kinda like two sum Leetcode question so I thought maybe put all numbers in hashmap. But that complicated things. Then maybe I thought we set a final pointer at the end of the list at n-1th index and create 2 pointers at 0th index and n-1th index. We can move the left pointer to the right but even though we can make a combination sum of 3 numbers with those 2 pointers moving and comparing the sum with the value at final pointer, it is not time efficient. Cuz we need to move final pointer to the left to check for other values.
Instead, i googled and omg there cant be a simple approach. Instead of looking for a combination sum of a+b+c to compare with value d, we instead can rearrange this formula.
A+b = d-c
Thus we simplified the problem by only needing to check 2 combination of 2 numbers. This combination of 2 numbers can be done by a double for loop, which is within the time limit. We can just store combination of a and b in a set and if d-c exists in set, we store d as ans. One careful note is that a,b,c can be same number as the pointers can point to same index. So if it is 7,7,7,21, answer should be 21. So the inner for loop should start from j in range(i,n), not j in range(i+1,n)
solution
import sys
input = sys.stdin.readline
n=int(input())
lst=[]
for _ in range(n):
lst.append(int(input()))
check=set()
for i in range(n):
for j in range(i,n):
check.add(lst[i]+lst[j])
ans=0
for k in range(n-1,-1,-1):
for z in range(k):
if lst[k]-lst[z] in check:
ans=max(ans,lst[k])
print(ans)complexity
n^2 log n time? and n space?
what is if something in check time complexity?
that is o(1) with hash collisions, so it is just n^2 time
Time Complexity:
Constructing the check set: O(n^2)
The nested loop iterates through all pairs of numbers in the input list, resulting in quadratic time complexity.
Finding the maximum sum: O(n^2)
The nested loop iterates through all pairs of numbers in the input list to find the maximum sum, resulting in quadratic time complexity.
Overall, the time complexity is O(n^2).
Space Complexity:
lst list: O(n)
The list stores the input numbers, resulting in linear space complexity.
check set: O(n^2)
The set may potentially store up to n^2 unique sums of pairs of numbers, resulting in quadratic space complexity.
Other variables: O(1)
The space occupied by other variables such as n, ans, i, j, k, and z is constant.
Overall, the space complexity is dominated by the check set, resulting in O(n^2).
In summary, the provided code has a time complexity of O(n^2) and a space complexity of O(n^2). It may be inefficient for large input sizes due to its quadratic time complexity.
