The trick to single pass array problems, and more

[sanjarcode]

Copying from activity_logger

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

[sanjarcode]

*algorithm design for some problems