DSA Arrays, Strings and Hashing Practice

Practise hash maps, two pointers, sliding windows and prefix sums on classic array and string problems.

Beginner8 problemsUpdated October 24, 2026

Review first: Hash Tables, Sets and Maps, Two Pointers, Sliding Window, Prefix Sums

1.Contains duplicate
Beginner
Write contains_duplicate(nums) that returns True if any value appears at least twice, in O(n) time. Test it on [1, 2, 3, 1] and [1, 2, 3, 4].
Show hint
Keep a set of values you have already seen.
Show solution
Python
def contains_duplicate(nums): seen = set() for x in nums: if x in seen: return True seen.add(x) return False print(contains_duplicate([1, 2, 3, 1])) print(contains_duplicate([1, 2, 3, 4]))
Output
True False
Checking membership in a set is O(1) on average, so the whole scan is O(n), compared with O(n²) for comparing every pair.
2.Two sum
Beginner
Write two_sum(nums, target) that returns the indexes of two different numbers adding up to target, in one pass. Test it with [2, 7, 11, 15], target 9, and [3, 2, 4], target 6.
Show hint
For each number, check whether target - number is already in a dictionary that maps values to indexes.
Show solution
Python
def two_sum(nums, target): index_of = {} for i, x in enumerate(nums): if target - x in index_of: return index_of[target - x], i index_of[x] = i return None print(two_sum([2, 7, 11, 15], 9)) print(two_sum([3, 2, 4], 6))
Output
(0, 1) (1, 2)
Storing each number only after checking it prevents a number from pairing with itself. O(n) time and space.

3.Valid palindrome

Beginner

A phrase is a palindrome if, after keeping only letters and digits and ignoring case, it reads the same both ways. Write is_palindrome(s) with two pointers and O(1) extra space. Test "A man, a plan, a canal: Panama" and "race a car".

Show hint

Move left forward and right backward past characters where isalnum() is false, then compare lowercase characters.

Show solution

Python

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

print(is_palindrome("A man, a plan, a canal: Panama"))
print(is_palindrome("race a car"))

Output

True
False

4.Best time to buy and sell
Beginner
Given daily prices, find the largest profit from buying on one day and selling on a later day (0 if no profit is possible). Test [7, 1, 5, 3, 6, 4] and [7, 6, 4, 3, 1].
Show hint
Walk through the prices once, remembering the lowest price so far and the best profit from selling today.
Show solution
Python
def max_profit(prices): lowest = float("inf") best = 0 for p in prices: lowest = min(lowest, p) best = max(best, p - lowest) return best print(max_profit([7, 1, 5, 3, 6, 4])) print(max_profit([7, 6, 4, 3, 1]))
Output
5 0
Buying at 1 and selling at 6 gives 5. A single pass with two variables is O(n) time and O(1) space.
5.Product of all other numbers
Intermediate
Return a list where each position holds the product of every other number, without using division. Test [1, 2, 3, 4].
Show hint
The answer at i is (product of everything to the left) × (product of everything to the right). Fill left products in one pass and multiply in right products in a second pass from the end.
Show solution
Python
def product_except_self(nums): result = [1] * len(nums) left = 1 for i in range(len(nums)): result[i] = left left *= nums[i] right = 1 for i in range(len(nums) - 1, -1, -1): result[i] *= right right *= nums[i] return result print(product_except_self([1, 2, 3, 4])) print(product_except_self([2, 0, 5]))
Output
[24, 12, 8, 6] [0, 10, 0]
This is the prefix-product idea from the prefix sums lesson. Avoiding division also handles zeros correctly.

6.Longest run after k replacements

Intermediate

You may change at most k characters of an uppercase string. Find the length of the longest substring of one repeated letter you can get. Test ("ABAB", 2) and ("AABABBA", 1).

Show hint

Sliding window. A window is valid if its length minus the count of its most common letter is at most k; shrink from the left when it is not.

Show solution

Python

from collections import Counter

def character_replacement(s, k):
    counts = Counter()
    left = best = top = 0
    for right, ch in enumerate(s):
        counts[ch] += 1
        top = max(top, counts[ch])
        while (right - left + 1) - top > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

print(character_replacement("ABAB", 2))
print(character_replacement("AABABBA", 1))

Output

4
4

The window only needs to grow when a better top is found, so leaving top as a historical maximum is safe and keeps the solution O(n).

7.Count subarrays with sum k

Intermediate

Count the contiguous subarrays whose sum is exactly k (numbers may be negative). Test ([1, 2, 3], 3) and ([1, -1, 0], 0).

Show hint

Prefix sums with a dictionary of how often each prefix total has occurred. Start with {0: 1}.

Show solution

Python

def subarray_sum(nums, k):
    seen = {0: 1}
    total = count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

print(subarray_sum([1, 2, 3], 3))
print(subarray_sum([1, -1, 0], 0))

Output

2
3

In the second list the subarrays [1, -1], [0] and [1, -1, 0] all sum to 0.

8.Most frequent words
Intermediate
Return the k most frequent words in a sentence, most frequent first, with ties broken alphabetically. Test the sentence "the cat and the dog and the bird" with k = 2.
Show hint
Count with Counter, then sort the items by (-count, word).
Show solution
Python
from collections import Counter def top_words(sentence, k): counts = Counter(sentence.split()) ranked = sorted(counts.items(), key=lambda item: (-item[1], item[0])) return [word for word, _ in ranked[:k]] print(top_words("the cat and the dog and the bird", 2)) print(top_words("b a c a b", 3))
Output
['the', 'and'] ['a', 'b', 'c']
Sorting by the negative count gives descending frequency while the word itself breaks ties in ascending order.

← All practice sets Learn Data Structures and Algorithms course →