def maxSubArray(nums):
    max_current = max_global = nums[0]
    for i in range(1, len(nums)):
        max_current = max(nums[i], max_current + nums[i])
        max_global = max(max_global, max_current)
    return max_global

"Can You Solve the 100 Locker Riddle?"

Your rich, eccentric uncle has left behind a mysterious will. You and 99 relatives are called to his mansion for the reading. Here’s the twist:

There are 100 lockers, each hiding a secret word. Each of you is assigned a number from 1 to 100. The rules are:

Heir 1 opens every locker.

Heir 2 closes every 2nd locker.

Heir 3 changes the state of every 3rd locker (opens if closed, closes if open).

This continues until Heir 100 changes the state of the 100th locker.

At the end, only the lockers that remain open will reveal the code to the safe.

Here’s the challenge:
Without going through all 100 steps, can you figure out which lockers will stay open?

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        myset = set()
        for i in nums:
            if i in myset:
                return True
            myset.add(i)
        return False

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        myset = set()
        l = 0
        for i in range(len(nums)):
            while(i-l>k):
                myset.remove(nums[l])
                l+=1
            if nums[i] in myset:
                return True
            myset.add(nums[i])
        return False

Examples to Understand Time Complexity

Example 1: Constant Time - O(1)
print("Hello World")
Explanation: The code runs in constant time because it prints "Hello World" only once, no matter the input size.
Time Complexity: O(1)

Example 2: Linear Time - O(n)
n = 8
for i in range(1, n + 1):
    print("Hello World !!!")
Explanation: The code prints "Hello World !!!" n times. As n grows, the runtime grows linearly.
Time Complexity: O(n)

Example 3: Logarithmic Time - O(log n)

n = 8
for i in range(1, n + 1, 2):
    print("Hello World !!!")
Explanation: The loop runs logarithmically because it skips half the steps each time.
Time Complexity: O(log n)

Example 4: Polynomial Time - O(n²)
n = 3
m = 3
arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]]
sum = 0

for i in range(n):
    for j in range(m):
        sum += arr[i][j]
print(sum)
Explanation: The code uses nested loops to sum all elements in a 2D array.
Time Complexity: O(n * m)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
       
        num_indices = {}
        for i, num in enumerate(nums):
            if num in num_indices and i - num_indices[num] <= k:
                return True
            num_indices[num] = i

        return False