Skip to main content

Poridhi: Arrays & Hashing

 

Arrays & hashing related problems:

This set of Python solutions covers a wide range of fundamental algorithm and data structure problems commonly found in technical interviews and real-world applications. The problems include searching for number pairs that meet a condition (Two Sum), identifying the best time to make a transaction for maximum profit (Best Time to Buy and Sell Stock), and calculating the largest possible sum from a continuous subarray (Maximum Subarray). Others like Product of Array Except Self and Valid Anagram test array manipulation and string comparison logic, while Group Anagrams organizes words into groups based on character content.

Further, this collection dives into more advanced concepts such as sliding window and dynamic programming. Problems like Longest Substring Without Repeating Characters, Minimum Window Substring, and Longest Palindromic Substring explore string manipulation using efficient techniques. Coin Change and the Combination Sum variations apply dynamic programming and backtracking to solve complex number combination tasks. These problems not only strengthen your problem-solving skills but also help you learn how to handle edge cases, optimize performance, and write clean, reusable code.

✅ Two Sum

def twoSum(nums, target):
    lookup = {}
    for i, num in enumerate(nums):
        if target - num in lookup:
            return [lookup[target - num], i]
        lookup[num] = i

✅ Best Time to Buy and Sell Stock

def maxProfit(prices):
    min_price, max_profit = float('inf'), 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

✅ Maximum Subarray

def maxSubArray(nums):
    current_sum = max_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

✅ Product of Array Except Self

def productExceptSelf(nums):
    n = len(nums)
    res = [1] * n

    left = 1
    for i in range(n):
        res[i] = left
        left *= nums[i]

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

    return res

✅ Valid Anagram

def isAnagram(s, t):
    return sorted(s) == sorted(t)

✅ Group Anagrams

from collections import defaultdict

def groupAnagrams(strs):
    anagrams = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))
        anagrams[key].append(s)
    return list(anagrams.values())

✅ Longest Substring Without Repeating Characters

def lengthOfLongestSubstring(s):
    seen = {}
    left = max_len = 0
    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        seen[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

✅ Minimum Window Substring

from collections import Counter

def minWindow(s, t):
    if not s or not t:
        return ""
    
    t_count = Counter(t)
    window_count = {}
    have, need = 0, len(t_count)
    res = [0, float('inf')]
    left = 0

    for right, char in enumerate(s):
        window_count[char] = window_count.get(char, 0) + 1

        if char in t_count and window_count[char] == t_count[char]:
            have += 1

        while have == need:
            if right - left < res[1] - res[0]:
                res = [left, right]
            window_count[s[left]] -= 1
            if s[left] in t_count and window_count[s[left]] < t_count[s[left]]:
                have -= 1
            left += 1

    l, r = res
    return s[l:r+1] if res[1] != float('inf') else ""

✅ Longest Palindromic Substring

def longestPalindrome(s):
    res = ""
    for i in range(len(s)):
        # Odd length
        l, r = i, i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l + 1 > len(res):
                res = s[l:r+1]
            l -= 1
            r += 1
        # Even length
        l, r = i, i+1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l + 1 > len(res):
                res = s[l:r+1]
            l -= 1
            r += 1
    return res

✅ Coin Change

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

✅ Combination Sum

def combinationSum(candidates, target):
    res = []

    def backtrack(start, path, total):
        if total == target:
            res.append(path[:])
            return
        if total > target:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, total + candidates[i])
            path.pop()
    
    backtrack(0, [], 0)
    return res

✅ Combination Sum II

def combinationSum2(candidates, target):
    res = []
    candidates.sort()

    def backtrack(start, path, total):
        if total == target:
            res.append(path[:])
            return
        if total > target:
            return
        prev = -1
        for i in range(start, len(candidates)):
            if candidates[i] == prev:
                continue
            path.append(candidates[i])
            backtrack(i + 1, path, total + candidates[i])
            path.pop()
            prev = candidates[i]

    backtrack(0, [], 0)
    return res

Comments

Post a Comment

Popular posts from this blog

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: ...
Post a Comment
Read more

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