Skip to main content

Poridhi: Stacks & Queues

 


Stacks & Queues related problems:

This collection of solutions tackles three classic problems often encountered in technical interviews and competitive programming. The Valid Parentheses problem checks whether a string has properly matched and ordered brackets using a stack. The Sliding Window Maximum efficiently finds the maximum value in every window of size k across an array using a deque, a popular sliding window pattern that ensures optimal performance. The Stock Span Problem simulates a real-world stock analysis scenario and calculates the number of consecutive days before today for which the stock price was less than or equal to today's, also utilizing a stack for efficient computation. These problems test understanding of stacks, queues, and sliding window techniques.

✅ Valid Parentheses

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    return not stack

✅ Sliding Window Maximum (Striver’s Sheet)

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()
    result = []

    for i in range(len(nums)):
        # Remove indices out of the current window
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Remove smaller values at the end of deque
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Start adding max from the kth window
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

✅ Stock Span Problem (using Stack)

def calculateSpan(prices):
    stack = []
    span = [0] * len(prices)

    for i in range(len(prices)):
        # Remove smaller or equal price indices
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()

        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)

    return span

Comments

Post a Comment

Popular posts from this blog

Data Recovery: DevOps pre-state learning

  Data Backup Data backup is the practice of copying data from a primary to a secondary location, to protect it in case of equipment failure, cyberattack, natural disaster or other data loss events. This can include documents, media files, configuration files, machine images, operating systems, and registry files. Essentially, any data that we want to preserve can be stored as backup data. Data Restore Data restore is the process of copying backup data from secondary storage and restoring it to its original location or a new location. A restore is performed to return data that has been lost, stolen or damaged to its original condition or to move data to a new location. Pilot Light A pilot light approach minimizes the ongoing cost of disaster recovery by minimizing the active resources, and simplifies recovery at the time of a disaster because the core infrastructure requirements are all in place. Warm Standby The warm standby approach involves ensuring that there is a scaled down, ...
Post a Comment
Read more

Poridhi: Basic Programming & Math

Basic Programming and math related problems: Extracting digits means breaking a number like 1234 into [1, 2, 3, 4], often using string conversion or modulo/division. Counting digits involves finding how many digits are in a number using length of a string or repeated division. Reversing an integer flips its digits (e.g., 123 becomes 321), with care for signs and 32-bit limits. A palindrome number reads the same forward and backward, often checked by comparing the original and reversed number. Armstrong numbers are those equal to the sum of their digits each raised to the number of digits, like 153 = 1³ + 5³ + 3³. To find the sum of all divisors of a number, loop through integers and check which divide the number without a remainder. Prime numbers are only divisible by 1 and themselves, and checking up to the square root is efficient. GCD, the greatest common divisor of two numbers, can be found using a simple loop or more efficiently with the Euclidean algorithm, which uses repeated mo...
Post a Comment
Read more