One Pass or Two passes

May be O(1) pass which indicates O(n) complexity.

Some problems from leetcode which needs O(n) complexity to solve.

53 Maximum Subarray
121 Best Time to Buy and Sell Stock
152 Maximum Product Subarray
238 Product of Array Except Self
739 Daily Temperatures
769 Max Chunks to Make Sorted
770 Max Chunks to Make Sorted II
821 Shortest Distance to a Character
845 Longest Mountain in Array

845. Longest Mountain in Array

Longest Mountain in Array - LeetCode

class Solution:
    def longestMountain(self, A: List[int]) -> int:
        if len(A)<3:return 0
        dp = [[1, 1 ] for i in range(len(A))]
        for i in range(1, len(A)):
            if A[i]>A[i-1]:
                dp[i][0] = dp[i-1][0]+1
            elif  A[i]<A[i-1]:
                dp[i][1] = max(dp[i-1]) + 1 if dp[i-1][0]>1 or  dp[i-1][1]>1  else 1
        _, res = max(dp, key=lambda x:x[1])
        return res if res>=3 else 0

828. Unique Letter String

https://leetcode.com/problems/unique-letter-string/

class Solution:
    def uniqueLetterString(self, S: str) -> int:
        index = {c: [-1, -1] for c in string.ascii_uppercase}
        res = 0
        for i2, c in enumerate(S):
            i0, i1 = index[c]
            res += (i2 - i1) * (i1 - i0)
            index[c] = [i1, i2]
        for c in index:
            i0, i1 = index[c]
            res += (len(S) - i1) * (i1 - i0)
        return res % (10**9 + 7)

Or we can write it in this way by using more memory.

class Solution:
    def uniqueLetterString(self, S: str) -> int:
        index = collections.defaultdict(list)
        for i, c in enumerate(S):
            index[c].append(i)
        res = 0
        for key in index:
            this_index = [-1] + index[key] + [len(S)]
            res += sum((k-j)*(j-i) for i,j,k in zip(this_index, this_index[1:],this_index[2:]))
        return res % (10**9+7)