Scribd
Upload
12 views3 pages

DSA Python Patterns

The document outlines key coding patterns for DSA interview preparation in Python, focusing on arrays, hash tables, two pointers, sliding windows, and stacks. It includes algorithms like Kadane's for maximum subarray, prefix sums for range queries, and techniques for problems such as the longest substring without repeating characters and the next greater element. Additionally, it provides a quick reference for time and space complexities associated with each pattern.

Uploaded by

buddha.gandhi8
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
12 views3 pages

DSA Python Patterns

The document outlines key coding patterns for DSA interview preparation in Python, focusing on arrays, hash tables, two pointers, sliding windows, and stacks. It includes algorithms like Kadane's for maximum subarray, prefix sums for range queries, and techniques for problems such as the longest substring without repeating characters and the next greater element. Additionally, it provides a quick reference for time and space complexities associated with each pattern.

Uploaded by

buddha.gandhi8
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

DSA Interview Prep — Python Patterns

Core patterns for product company coding rounds. Focus: Array, Hash Table, Two
Pointers, Sliding Window, Stack.

1. Array Patterns
Kadane's Algorithm — Maximum Subarray
Find contiguous subarray with the largest sum. O(n) time, O(1) space.

def maxSubArray(nums):
max_sum = cur_sum = nums[0]
for n in nums[1:]:
cur_sum = max(n, cur_sum + n) # restart or extend
max_sum = max(max_sum, cur_sum)
return max_sum

Prefix Sum Pattern


Precompute cumulative sums for O(1) range queries. Used in subarray sum problems.

# Subarray Sum Equals K


def subarraySum(nums, k):
count = prefix = 0
seen = {0: 1} # prefix_sum: frequency
for n in nums:
prefix += n
count += [Link](prefix - k, 0)
seen[prefix] = [Link](prefix, 0) + 1
return count

2. Two Pointers
Classic Two Sum (Sorted Array)
def twoSum(numbers, target):
l, r = 0, len(numbers) - 1
while l < r:
s = numbers[l] + numbers[r]
if s == target: return [l+1, r+1]
elif s < target: l += 1
else: r -= 1

Container With Most Water


def maxArea(height):
l, r, res = 0, len(height)-1, 0
while l < r:
res = max(res, min(height[l], height[r]) * (r - l))
if height[l] < height[r]: l += 1
else: r -= 1
return res

3. Sliding Window
Variable Window — Longest Substring Without Repeating
def lengthOfLongestSubstring(s):
seen = {} # char: last index
l = res = 0
for r, c in enumerate(s):
if c in seen and seen[c] >= l:
l = seen[c] + 1 # shrink left
seen[c] = r
res = max(res, r - l + 1)
return res

Fixed Window — Max Average Subarray


def findMaxAverage(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i-k] # slide
best = max(best, window)
return best / k

4. Stack Patterns
Monotonic Stack — Next Greater Element
def nextGreaterElement(nums):
res = [-1] * len(nums)
stack = [] # indices, decreasing order
for i, n in enumerate(nums):
while stack and nums[stack[-1]] < n:
res[[Link]()] = n
[Link](i)
return res

5. Quick Reference: Time Complexities


Algorithm Time Space Pattern
Kadane's O(n) O(1) Array
Prefix Sum O(n) O(n) Hash + Array
Two Pointers O(n) O(1) Sorted Array
Sliding Window O(n) O(k) Substring
Monotonic Stack O(n) O(n) NGE problems
Frequency Map O(n) O(n) Anagram/Count

You might also like