You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
All single pass 1D array problems rely on the "knowing" what has happened in the past - i.e possibility of creating a fast lookup structure for the till-seen part of the array.
This fast lookup structure may be a number (e.g. in case of Kadane's algorithm) or a hashmap or a heap, anything.
Approximately, this should takeo(n) space and/or o(n) lookup time (small O notation).
If this is not possible - i.e. one cannot create a structure at all or it exceeds the said bound, two (or more) loops are inevitable.
*more than one loop is inevitable
This thinking could be extended to more dimensional structures like n-dimensional arrays or trees or graphs or a combination.
Why this might work - noob level information theory
The text was updated successfully, but these errors were encountered:
Copying from activity_logger
The text was updated successfully, but these errors were encountered: