Leetcode Problem 1500-1599
1502. Can Make Arithmetic Progression From Sequence 🌟
Simple Solution
- Sort the array.
- Check if the difference between any two consecutive elements is the same or not.
- TC: O(NlogN): For sorting
- SC: O(1): Excluding sorting space, No extra space required. OR
-
| **SC: O(logN) |
|
O(N)**: Considering Space required for internal sorting. in C++ its O(logN) for py its O(N). |
O(N^2) Time O(1) Space solution
- Check for each element of array and return the ans.
O(N) Time O(N) Space optimization
- Use map to store if the number appeared before or not.
- If it appeared add frequency to ans.else add it to map.
Simulation
- If k >= n, then the max element will always win the game, as it will not change its position from 0 index.
- If k < n, then we need to simulate the game.
- We need to keep track of the current winner and the number of consecutive wins.
- If the current winner wins, then we increment the number of consecutive wins.
- If the current winner loses, then we set the number of consecutive wins to 1.
- If the number of consecutive wins is equal to k, then we return the current winner.
- Else, we return the last winner.
- TC: O(n)
- SC: O(1)
O(N) Time O(1) Space solution