# Part B
#### 901. Online Stock Span

class StockSpanner:
    def __init__(self):
        self.stack =[]
        
    def span(self,price):
        s=1
        while self.stack and self.stack[-1][0] <= price:
            s+=self.stack[-1][1]
            self.stack.pop()
            
        self.stack.append((price,s))
        
        return s
    
spanner=StockSpanner()

print(spanner.span(100)) # 1
print(spanner.span(80))  # 1
print(spanner.span(60))  # 1
print(spanner.span(70))  # 2
print(spanner.span(60))  # 1
print(spanner.span(75))  # 4
print(spanner.span(85))  # 6

---

### #61. Rotate List

class ListNode:
    def __init__(self,data=0,next=None):
        self.data=data 
        self.next=next 
        
    
def roateright(head,k):
    l=1
    tail=head
    while tail.next:
        tail=tail.next
        l+=1
        
    tail.next=head
    
    k=k%l
    step_to_new_tail=l-k
    new_tail=head
    
    for _ in range(step_to_new_tail-1):
        new_tail=new_tail.next
    new_head=new_tail.next
    new_tail.next=None
    
    
    return new_head
    

def print_linked_list(head):
    result = []
    while head:
        result.append(str(head.data))
        head = head.next
    print(" -> ".join(result))
    
    
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)

n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5

head = n1
k=2

print_linked_list(head)
result=roateright(head,k)
print_linked_list(result)

    

---

### #19. Remove Nth Node From End of List

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd_optimized(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy

    # Move fast pointer n + 1 steps ahead
    for _ in range(n + 1):
        fast = fast.next

    # Move both pointers together until fast reaches the end
    while fast:
        fast = fast.next
        slow = slow.next

    # Delete the node
    slow.next = slow.next.next
    return dummy.next

def print_linked_list(head):
    values = []
    while head:
        values.append(str(head.val))
        head = head.next
    print(" -> ".join(values) if values else "Empty List")

# 🛠️ Manually create the linked list [1, 2, 3, 4, 5]
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

# Link nodes
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

head = node1
n = 2

print("Original list:")
print_linked_list(head)

# Test optimized
print("\nAfter removing nth node from end (Optimized):")
result_optimized = removeNthFromEnd_optimized(head, n)
print_linked_list(result_optimized)

# Expected Output:
# Original list:
# 1 -> 2 -> 3 -> 4 -> 5
#
# After removing nth node from end (Optimized):
# 1 -> 2 -> 3 -> 5

---

### #424. Longest Repeating Character Replacement

from  collections import Counter

def ref(s,k):
    c=Counter()
    l=0
    req=0
    maxf=0
    
    for r in range(len(s)):
        c[s[r]]+=1
        maxf=max(maxf,c[s[r]])
        
        while (r-l+1)-maxf > k:
            c[s[l]]-=1
            L+=1
        
        req=max(req,r-l+1)
    
    return req

s="ABAB"
k=2
print(ref(s,k)) 

### #11. Container With Most Water

def maxArea(h):
    l, r = 0, len(h) - 1
    maxA = 0

    while l < r:
        ht = min(h[l], h[r])       
        wd = r - l                  
        area = ht * wd            
        maxA = max(maxA, area)     

        if h[l] < h[r]:
            l += 1
        else:
            r -= 1

    return maxA

h = [1,8,6,2,5,4,8,3,7]
print(maxArea(h))

### #238. Product of Array Except Self

def product_except_self(nums):
    n = len(nums)
    res = [1] * n
    l, r = 1, 1

    for i in range(n):
        res[i] *= l
        res[n - 1 - i] *= r
        l *= nums[i]
        r *= nums[n - 1 - i]

    return res

nums = [1, 2, 3, 4]
print(product_except_self([1, 2, 3, 4]))  # ➤ [24, 12, 8, 6]

# PART A

### #303. Range Sum Query

class NumArray:
    def __init__(self, nums):
        self.prefix_sum = [0]
        for num in nums:
            self.prefix_sum.append(self.prefix_sum[-1] + num)

    def sumRange(self, left, right):
        return self.prefix_sum[right + 1] - self.prefix_sum[left]

nums = [1, 2, 3, 4, 5]
queries = [(0, 2), (1, 3), (2, 4)]


brute = NumArray(nums)
for left, right in queries:
    result = brute.sumRange(left, right)
    print(f"sumRange({left}, {right}) = {result}")

---
### #560. Subarray Sum Equals K

def subarray(nums,k):
    prsum=0
    count=0
    pmap={0:1}
    
    for num in nums:
        prsum+=num
        
        if prsum-k in pmap:
            count+=pmap[prsum-k]
            
        pmap[prsum]=pmap.get(prsum,0)+1
        
    return count

nums = [1, 2, 3, -1, 1, 2, 1]
k = 3
print(subarray(nums,k))

---

### #125. Valid Palindrome

def palii(s):
    l,r=0,len(s)-1
    
    while l<r:
        while l<r and not s[l].isalnum():
            l+=1
        while l<r and not s[r].isalnum():
            r-=1
            
        if s[l].lower() != s[r].lower():
            return False
        l+=1
        r-=1
    return True
print(palii("A man, a plan, a canal: Panama"))

---
### #167. Two Sum II

def twosum(num,t):
    l,r=0,len(num)-1
    
    while l<r:
        c=num[l]+num[r]
        if c==t:
            return [l+1,r+1]
        elif c<t:
            l+=1
        else:
            r-=1
    return []

num = [2, 3, 4, 8, 11, 15]
tar = 11

print(twosum(num,tar)) 

---
### #643: Maximum Average Subarray I

def ave(nums,k):
    ws=sum(nums[:k])
    mx=ws 
    for i in range(k,len(nums)):
        ws+=nums[i]-nums[i-k]
        mx=max(mx,ws)
    return mx/float(k)

nums=[1, 12, -5, -6, 50, 3]
k=4
print(ave(nums,k)) # 12.75

---
### #3: Longest Substring Without Repeating Characters

def repep(s):
    seen=set()
    mx=0
    l=0
    
    for r in range(len(s)):
         while s[r] in seen:
             seen.remove(s[r])
             l+=1
         seen.add(s[r])
         mx=max(mx,r-l+1)
    return mx
s="abcabcbb"
print(repep(s)) # 3

---
### #141. Linked List Cycle

class listNode:
    def __init__(self,data=0,next=None):
        self.data=data
        self.next=next
        
def cycyle(head):
    s=f=head
    while f and f.next:
        s=s.next
        f=f.next.next
        if s==f:
            return True
    return False

n1 = listNode(1)
n2 = listNode(2)
n3 = listNode(3)
n4 = listNode(4)

n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n2  

head=n1

if cycyle(head):
    print("cycle detected")
else:
    print("no cycle detected")
            

---

### #876: Middle of the Linked List

class listNode:
    def __init__(self,data=0,next=None):
        self.data=data
        self.next=next
        
def cycyle(head):
    s=f=head
    while f and f.next:
        s=s.next
        f=f.next.next
        
    return s

n1 = listNode(1)
n2 = listNode(2)
n3 = listNode(3)
n4 = listNode(4)
n5 = listNode(5)

n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5 

head=n1

result=cycyle(head)
if result:
    print("Cycle detected at node with value:", result.data)    

---

### #206: Reverse Linked List

class ListNode:
    def __init__(self, value=0 ,next=None):
        self.value = value
        self.next = None
        
def rev(head):
    p=None
    c=head
    while c:
        next_node=c.next                
        c.next=p
        p=c
        c=next_node
    return p

def printL(head):
    r=[]
    while head:
        r.append(str(head.value))
        head=head.next
    print("->".join(r))
    
n1=ListNode(1)
n2=ListNode(2)
n3=ListNode(3)
n4=ListNode(4)

n1.next=n2
n2.next=n3
n3.next=n4
n4.next=None
head=n1

printL(head)
result=rev(head)
printL(result)

---

### #496. Next Greater Element I

def next(n1,n2):
    stack=[]
    map={}
    
    for num in n2:
        while stack and stack[-1]<num:
            prev=stack.pop()
            map[prev]=num
        stack.append(num)
        
    return [map.get(i,-1) for i in n1]

n1 = [4, 1, 2]
n2 = [1, 3, 4, 2]

print(next(n1,n2))  # Output: [-1, 3, -1]

---

### #739. Daily Temperatures

def temp(num):
    n=len(num)
    ans=[0]*n
    stack=[]
    
    for i in range(n):
        while stack and num[i] >  num[stack[-1]]:
            prev=stack.pop()
            ans[prev]=i-prev
        stack.append(i)
    return ans
num=[1,2,1,3,4,5,6,7,8,9]
print(temp(num)) # Output: [0, 1, 0, 1, 1, 1, 1, 1, 1, 0]

---