# Problem Solving on Online Coding Platforms

:::info
PART B
:::

*++**🧩 LeetCode 142: Linked List Cycle II**++
📝 Problem Statement:
Given the head of a linked list, return the node where the cycle begins.
If there is no cycle, return null.
There is a cycle in a linked list if there is a node that can be visited again by continuously following the next pointer.*

*🧪 Example 1:
Input:
head = [3,2,0,-4], pos = 1
Output: Node with value 2
Explanation: The tail connects to the second node (index 1), forming a cycle starting at node with value 2*

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


def detectCycle_brute(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            return current
        visited.add(current)
        current = current.next
    return None

#optimized using slow and fast 
def look(head):
    slow=fast=head
    
    while fast:
        slow=slow.next
        fast=fast.next.next
        
        if slow==fast:
            break
    else:
        return None
    
    slow=head
    
    while slow!=fast:
        slow=slow.next
        fast=fast.next
     return slow    

# 🛠 Manually Create Linked List with a Cycle
# Example: [3,2,0,-4], pos = 1 (tail connects to node with value 2)

# Create nodes
node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)

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

head = node1

cycle_node = detectCycle_brute(head)
if cycle_node:
    print("Cycle detected! Cycle starts at node with value:", cycle_node.val)
else:
    print("No cycle detected.")

*++**🧩 LeetCode 19: Remove Nth Node From End of List**++
📝 Problem Statement:
Given the head of a linked list, remove the nth node from the end of the list and return its head.*

*🧪 Example 1:
makefile
Copy
Edit
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]*

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

*++**🧩 LeetCode 901: Online Stock Span**++
📝 Problem Statement:
Design an algorithm that collects daily stock prices and returns the span of that stock’s price for the current day.
The span of the stock’s price today is defined as the number of consecutive days (including today) the price was less than or equal to today’s price.
Implement the StockSpanner class:
StockSpanner() initializes the object.
int next(int price) returns the span of the stock’s price given that today’s price is price.*

*🧪 Example 1:
makefile
Copy
Edit
Input: ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output: [null, 1, 1, 1, 2, 1, 4, 6]*

class StockSpanner:
    def __init__(self):
        self.stack = []  

    def next(self, price):
        span = 1

        while self.stack and self.stack[-1][0] <= price:
            span += self.stack[-1][1]
            self.stack.pop()

        self.stack.append((price, span))
        return span


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

*++**🧩 LeetCode 82: Remove Duplicates from Sorted List II**++
📝 Problem Statement:
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well..*

*🧪 Example 1:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]*

# ✅ Definition for singly-linked list node
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# ⚙️ Function to remove all duplicates (keep only unique values)
def deleteDuplicates(head):
    dummy = ListNode(0, head)
    prev = dummy

    while head:
        if head.next and head.val == head.next.val:
            # Skip all nodes with same value
            while head.next and head.val == head.next.val:
                head = head.next
            prev.next = head.next  # unlink duplicates
        else:
            prev = prev.next
        head = head.next

    return dummy.next

# 🧪 Manual linked list: [1, 2, 3, 3, 4, 4, 5]
node1 = ListNode(1)
node2 = ListNode(2)
node3a = ListNode(3)
node3b = ListNode(3)
node4a = ListNode(4)
node4b = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3a
node3a.next = node3b
node3b.next = node4a
node4a.next = node4b
node4b.next = node5

head = node1


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


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

print("\nAfter removing duplicates (keep only distinct values):")
new_head = deleteDuplicates(head)
print_linked_list(new_head)

:::info
PART A
:::

*++**🧩 LeetCode 303: Range Sum Query – Immutable**++
📝 Problem Statement:
Given an integer array nums, handle multiple queries of the following type:
Calculate the sum of the elements of nums between indices left and right inclusive, where left <= right.*

*Implement the NumArray class:*
*- NumArray(int[] nums) Initializes the object with the integer array nums.*
*- int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + ... + nums[right]).*

*🧪 Example 1:
Input: ["NumArray", "sumRange", "sumRange", "sumRange"]
[[[1,2,3,4,5]], [0,2], [1,3], [2,4]]
Output: [null, 6, 9, 12]*

class NumArray_Brute:
    def __init__(self, nums):
        self.nums = nums

    def sumRange(self, left, right):
        return sum(self.nums[left:right + 1])



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


brute = NumArray_Brute(nums)


print("🔎 Brute Force Results:")
for left, right in queries:
    result = brute.sumRange(left, right)
    print(f"sumRange({left}, {right}) = {result}")

*++**🧩 LeetCode 560: Subarray Sum Equals K**++
📝 Problem Statement:
Given an integer array nums and an integer k, return the total number of continuous subarrays whose sum equals to k.*

*🧪 Example 1:
Input: nums = [1,1,1], k = 2
Output: 2 (→ subarrays [1,1] at indices [0,1] and [1,2])*

# 🐢 Brute Force
def subarraySum_brute(nums, k):
    count = 0
    n = len(nums)
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count


# ⚡ Optimized using Prefix Sum + HashMap
def subarraySum_optimized(nums, k):
    prefix_sum = 0
    count = 0
    prefix_map = {0: 1}
    for num in nums:
        prefix_sum += num
        if prefix_sum - k in prefix_map:
            count += prefix_map[prefix_sum - k]
        prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1
    return count

# 🧪 Manual Input
nums = [1, 2, 3, -1, 1, 2, 1]
k = 3

# 🖨️ Run Tests
print("🔎 Brute Force Result:")
print("Count of subarrays with sum =", k, "=>", subarraySum_brute(nums, k))

print("\n⚡ Optimized Result:")
print("Count of subarrays with sum =", k, "=>", subarraySum_optimized(nums, k))

*++**🧩 LeetCode 125: Valid Palindrome**++
📝 Problem Statement:
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward.Return True if it is a palindrome, False otherwise.*

*🧪 Example 1:
Input: "A man, a plan, a canal: Panama"
Output: True
Input: "race a car"
Output: False*

# 🐢 Brute Force (Clean & Reverse Compare)
def isPalindrome_brute(s):
    clean = ''.join(c.lower() for c in s if c.isalnum())
    return clean == clean[::-1]

# ⚡ Optimized Two-Pointer
def isPalindrome_optimized(s):
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        # Compare
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

# 🧪 Manual Input
inputs = [
    "A man, a plan, a canal: Panama",
    "race a car",
    " ",
    "0P"
]

# 🖨️ Run Tests
print("🔎 Brute Force Results:")
for s in inputs:
    print(f"'{s}' => {isPalindrome_brute(s)}")

print("\n⚡ Optimized Results:")
for s in inputs:
    print(f"'{s}' => {isPalindrome_optimized(s)}")
    
    #🔎 Brute Force Results:
# 'A man, a plan, a canal: Panama' => True
# 'race a car' => False
# ' ' => True
# '0P' => False

# ⚡ Optimized Results:
# 'A man, a plan, a canal: Panama' => True
# 'race a car' => False
# ' ' => True
# '0P' => False

*++**🧩 LeetCode 167: Two Sum II – Input Array Is Sorted**++
📝 Problem Statement:
Given a 1-indexed, sorted array of integers numbers that is sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers (1-indexed).
You must use only constant extra space.*

*🧪 Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
(→ because 2 + 7 = 9)*

# 🐢 Brute Force (O(n^2))
def twoSum_brute(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return []

# ⚡ Optimized Two-Pointer Approach (O(n))
def twoSum_optimized(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return [left + 1, right + 1]
        elif current < target:
            left += 1
        else:
            right -= 1
    return []

# 🧪 Manual Input
numbers = [2, 3, 4, 8, 11, 15]
target = 11


print("🔎 Brute Force Result:")
print(f"Indices of two numbers summing to {target}:", twoSum_brute(numbers, target))

print("\n⚡ Optimized Result:")
print(f"Indices of two numbers summing to {target}:", twoSum_optimized(numbers, target))

*++**🧩 LeetCode 643: Maximum Average Subarray I**++
📝 Problem Statement:
You are given an integer array nums consisting of n elements, and an integer k.
Find the contiguous subarray of length k that has the maximum average value and return this value.
You must solve the problem in O(n) time complexity.*

*🧪 Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75
(→ subarray [12, -5, -6, 50] has average = (12 - 5 - 6 + 50)/4 = 12.75)*

# ✅ Brute Force (O(n*k)) — for understanding
def findMaxAverage_brute(nums, k):
    max_avg = float('-inf')
    for i in range(len(nums) - k + 1):
        current_sum = sum(nums[i:i+k])
        max_avg = max(max_avg, current_sum / k)
    return max_avg


# ⚡ Optimized (O(n)) using Sliding Window
def findMaxAverage_optimized(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum / float(k)


# 🧪 Manual Input
nums = [1, 12, -5, -6, 50, 3]
k = 4


print("🔎 Brute Force Result:")
print("Max Average:", findMaxAverage_brute(nums, k))

print("\n⚡ Optimized Result:")
print("Max Average:", findMaxAverage_optimized(nums, k))
# 🔎 Brute Force Result:
# Max Average: 12.75

# ⚡ Optimized Result:
# Max Average: 12.75

*++**🧩 LeetCode 3: Longest Substring Without Repeating Characters**++
📝 Problem Statement:
Given a string s, find the length of the longest substring without repeating characters.*

*🧪 Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.*

# ✅ Brute Force (O(n^3)) – Check all substrings
def lengthOfLongestSubstring_brute(s: str) -> int:
    max_len = 0
    n = len(s)
    for i in range(n):
        for j in range(i+1, n+1):
            if len(set(s[i:j])) == (j - i):
                max_len = max(max_len, j - i)
    return max_len


# ⚡ Optimized (O(n)) – Sliding Window with HashSet
def lengthOfLongestSubstring_optimized(s: str) -> int:
    seen = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len


# 🧪 Manual Inputs
inputs = ["abcabcbb", "bbbbb", "pwwkew", ""]

# 🖨️ Run Tests
print("🔎 Brute Force Results:")
for s in inputs:
    print(f"Input: '{s}' → Output: {lengthOfLongestSubstring_brute(s)}")

print("\n⚡ Optimized Results:")
for s in inputs:
    print(f"Input: '{s}' → Output: {lengthOfLongestSubstring_optimized(s)}")
    
# 🔎 Brute Force Results:
# Input: 'abcabcbb' → Output: 3
# Input: 'bbbbb' → Output: 1
# Input: 'pwwkew' → Output: 3
# Input: '' → Output: 0

# ⚡ Optimized Results:
# Input: 'abcabcbb' → Output: 3
# Input: 'bbbbb' → Output: 1
# Input: 'pwwkew' → Output: 3
# Input: '' → Output: 0

*++**🧩 LeetCode 141: Linked List Cycle**++
📝 Problem Statement:
Given head, the head of a linked list, determine if the linked list has a cycle in it.A linked list has a cycle if any node is visited more than once while traversing the list.Return True if there is a cycle in the linked list. Otherwise, return False.*

*🧪 Example 1:
Input: head = [3,2,0,-4] → tail connects to node index 1
Output: True*

# ✅ Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None


# 🐢 Brute Force – Using a set to track visited nodes
def hasCycle_brute(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            return True
        visited.add(current)
        current = current.next
    return False


# ⚡ Optimized – Floyd's Cycle Detection (Tortoise & Hare)
def hasCycle_optimized(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False



node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)

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

head_with_cycle = node1


a = ListNode(1)
b = ListNode(2)
a.next = b

head_without_cycle = a

# 🖨️ Test Outputs
print("🔎 Brute Force:")
print("Has cycle (should be True):", hasCycle_brute(head_with_cycle))
print("Has cycle (should be False):", hasCycle_brute(head_without_cycle))

print("\n⚡ Optimized:")
print("Has cycle (should be True):", hasCycle_optimized(head_with_cycle))
print("Has cycle (should be False):", hasCycle_optimized(head_without_cycle))

# 🔎 Brute Force:
# Has cycle (should be True): True
# Has cycle (should be False): False

# ⚡ Optimized:
# Has cycle (should be True): True
# Has cycle (should be False): False

*++**🧩 LeetCode 876: Middle of the Linked List**++
📝 Problem Statement:
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.*

*🧪 Example 1:
Input: head = [1,2,3,4,5]
Output: Node with value 3
Explanation: The middle node of the list is 3.*

*🧪 Example 2:
Input: head = [1,2,3,4,5,6]
Output: Node with value 4
Explanation: There are two middle nodes, 3 and 4. Return 4.*

# ✅ Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 🐢 Brute Force – Count Length, Then Traverse Again (O(n))
def middleNode_brute(head):
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    mid = length // 2
    curr = head
    for _ in range(mid):
        curr = curr.next

    return curr


# ⚡ Optimized – Two Pointers (O(n)), one pass
def middleNode_optimized(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


# 🛠️ Helper: Print a linked list from a given node
def print_linked_list(head):
    values = []
    while head:
        values.append(str(head.val))
        head = head.next
    print(" -> ".join(values))


# 🧪 Manual Input: [1,2,3,4,5,6]
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n6 = ListNode(6)

# Link nodes
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6

head = n1

# 🖨️ Outputs
print("🔗 Full List:")
print_linked_list(head)

print("\n🔎 Brute Force Middle Node:")
middle = middleNode_brute(head)
print_linked_list(middle)

print("\n⚡ Optimized Middle Node:")
middle = middleNode_optimized(head)
print_linked_list(middle)

# 🔗 Full List:
# 1 -> 2 -> 3 -> 4 -> 5 -> 6

# 🔎 Brute Force Middle Node:
# 4 -> 5 -> 6

# ⚡ Optimized Middle Node:
# 4 -> 5 -> 6

*++**🧩 LeetCode 206: Reverse Linked List**++
📝 Problem Statement:
Given the head of a singly linked list, reverse the list, and return the reversed list.*

*🧪 Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]*

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


# 🔁 Brute Force – Use stack to reverse (Extra space)
def reverseList_brute(head):
    stack = []
    curr = head
    while curr:
        stack.append(curr.val)
        curr = curr.next

    dummy = ListNode(0)
    curr = dummy
    for val in reversed(stack):
        curr.next = ListNode(val)
        curr = curr.next

    return dummy.next


# ⚡ Optimized – Iterative reverse in-place (O(n), O(1))
def reverseList_optimized(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev


def print_linked_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result))


# 🧪 Manual Input: [1,2,3,4,5]
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


print("🔗 Original List:")
print_linked_list(head)

print("\n🔎 Brute Force Reversed List:")
rev1 = reverseList_brute(head)
print_linked_list(rev1)

# For optimized, recreate the original list since brute reversed it
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

print("\n⚡ Optimized Reversed List:")
rev2 = reverseList_optimized(head)
print_linked_list(rev2)

*++**🧩 LeetCode 92: Reverse Linked List II**++
📝 Problem Statement:
Given the head of a singly linked list and two integers left and right where 1 <= left <= right <= length of list, reverse the nodes of the list from position left to position right, and return the reversed list.*

*🧪 Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]*

# ✅ Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 🐢 Brute Force – Extract + reverse + reconnect (Extra space)
def reverseBetween_brute(head, left, right):
    if not head or left == right:
        return head

    vals = []
    curr = head
    while curr:
        vals.append(curr.val)
        curr = curr.next

    vals[left - 1:right] = reversed(vals[left - 1:right])

    dummy = ListNode(0)
    curr = dummy
    for val in vals:
        curr.next = ListNode(val)
        curr = curr.next

    return dummy.next


# ⚡ Optimized – In-place reverse between left and right
def reverseBetween_optimized(head, left, right):
    if not head or left == right:
        return head

    dummy = ListNode(0, head)
    prev = dummy

    # Move prev to node before 'left'
    for _ in range(left - 1):
        prev = prev.next

    # Reverse from left to right
    reverse_prev = None
    curr = prev.next
    for _ in range(right - left + 1):
        next_temp = curr.next
        curr.next = reverse_prev
        reverse_prev = curr
        curr = next_temp

    # Connect segments
    prev.next.next = curr
    prev.next = reverse_prev

    return dummy.next


# 🛠️ Helper to print linked list
def print_linked_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result))


# 🧪 Manual Input: [1,2,3,4,5], left = 2, right = 4
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
left, right = 2, 4

print("🔗 Original List:")
print_linked_list(head)

print("\n🔎 Brute Force Reversed Sublist:")
reversed_brute = reverseBetween_brute(head, left, right)
print_linked_list(reversed_brute)

# Rebuild the original list for optimized
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

print("\n⚡ Optimized Reversed Sublist:")
reversed_opt = reverseBetween_optimized(head, left, right)
print_linked_list(reversed_opt)

# 🔗 Original List:
# 1 -> 2 -> 3 -> 4 -> 5

# 🔎 Brute Force Reversed Sublist:
# 1 -> 4 -> 3 -> 2 -> 5

# ⚡ Optimized Reversed Sublist:
# 1 -> 4 -> 3 -> 2 -> 5

*++**🧩 LeetCode 496: Next Greater Element I**++
📝 Problem Statement:
The next greater element of some element x in an array is the first greater element to the right of x in the same array.
You are given two distinct integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each x in nums1, find the next greater element of x in nums2. If it does not exist, return -1 for this number.*

*🧪 Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation:
For 4, there is no greater element in nums2 → -1
For 1, the next greater is 3
For 2, there is no greater → -1
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]*

# 🐢 Brute Force: Check every element to the right in nums2
def nextGreaterElement_brute(nums1, nums2):
    result = []
    for num in nums1:
        found = False
        next_greater = -1
        for i in range(len(nums2)):
            if nums2[i] == num:
                for j in range(i + 1, len(nums2)):
                    if nums2[j] > num:
                        next_greater = nums2[j]
                        break
                break
        result.append(next_greater)
    return result


# ⚡ Optimized: Use stack + hashmap (Monotonic Stack)
def nextGreaterElement_optimized(nums1, nums2):
    stack = []
    hashmap = {}

    for num in nums2:
        while stack and num > stack[-1]:
            prev = stack.pop()
            hashmap[prev] = num
        stack.append(num)

    return [hashmap.get(num, -1) for num in nums1]


# 🧪 Manual Input
nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]

# 🖨️ Outputs
print("🔎 Brute Force Output:")
print(nextGreaterElement_brute(nums1, nums2))

print("\n⚡ Optimized Output:")
print(nextGreaterElement_optimized(nums1, nums2))

# 🔎 Brute Force Output:
# [-1, 3, -1]

# ⚡ Optimized Output:
# [-1, 3, -1]

*++**🧩 LeetCode 739: Daily Temperatures**++
📝 Problem Statement:
Given an array of integers temperatures representing the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature.
If there is no future day for which this is possible, put 0 instead.*

*🧪 Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]*

# 🐢 Brute Force – Check for every future day
def dailyTemperatures_brute(temperatures):
    n = len(temperatures)
    answer = [0] * n

    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i
                break

    return answer


# ⚡ Optimized – Monotonic Stack (O(n))
def dailyTemperatures_optimized(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []  # stores indices

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index
        stack.append(i)

    return answer


# 🧪 Manual Input
temps = [73, 74, 75, 71, 69, 72, 76, 73]

# 🖨️ Outputs
print("🔎 Brute Force Output:")
print(dailyTemperatures_brute(temps))

print("\n⚡ Optimized Output:")
print(dailyTemperatures_optimized(temps))