HWI Practice
HWI Practice
1. Subarrays with Even Sum Starting with Odd Number
Problem: Find the number of subarrays with an even sum that start with an odd number.
Approach: Prefix sum + parity tracking.
GFG Link: Find the number of subarrays having even sum
Leetcode Link: 1524. Number of Sub-arrays With Odd Sum
2. Maximum Sum of Non-Adjacent Elements
Problem: Find the maximum subarray sum where no two elements are adjacent.
Approach: Dynamic Programming (DP).
LeetCode Link: House Robber
3. Range Increment Queries on Array
Problem: Process queries to increment ranges and print the final array.
Approach: Difference array or Segment Tree.
GFG Link: Range Update Queries
4. Prefix Character Count
Problem: For each index, count occurrences of the character in the prefix.
Approach: Hash map or frequency array.
LeetCode Link: Find All Anagrams in a String (variant)
5. XOR Queries on Subarrays
Problem: Answer XOR queries for ranges [l, r].
Approach: Prefix XOR array.
LeetCode Link: XOR Queries of a Subarray
6. Count Increasing Triplets
Problem: Count triplets (i, j, k) where A[i] < A[j] < A[k].
Approach: Binary Indexed Tree (Fenwick Tree) or DP.
LeetCode Link: Increasing Triplet Subsequence
7. Sum of All Subarrays
Problem: Compute the sum of all subarrays modulo 109+7109+7.
Approach: Contribution of each element.
GFG Link: Sum of All Subarrays
8. K-th Smallest Unique Element
Problem: Find the k-th smallest element appearing exactly once.
Approach: Hash map + sorting.
LeetCode Link: Kth Distinct String (variant)
9. String Score Based on Pattern Occurrences
Problem: Score string S by adding len(P)^2 for each occurrence of P.
Approach: KMP or Rabin-Karp.
LeetCode Link: Count Occurrences in String
10. Longest Contiguous Arithmetic Subarray
Problem: After range arithmetic sequence assignments, find the longest arithmetic subarray.
Approach: Segment Tree with lazy propagation.
GFG Link: Arithmetic Subarrays
11. Maximum Score with Penalty
Problem: Choose elements to maximize score while subtracting penalties.
Approach: DP (0/1 Knapsack variant).
LeetCode Link: Maximum Subarray Sum with Penalty
12. Maximize Tasks with Limited Skips
Problem: Complete maximum tasks with k skips allowed.
Approach: Greedy + Priority Queue.
LeetCode Link: Task Scheduler
13. Climbing Steps with Magic Potions
Problem: Climb steps using potions to replenish energy.
Approach: Greedy + Binary Search.
LeetCode Link: Jump Game
14. Maximum Profit with Cooldown
Problem: Maximize job profit with a 1-day cooldown.
Approach: DP with state tracking.
LeetCode Link: Best Time to Buy and Sell Stock with Cooldown
15. Minimize Spending with Discount Vouchers
Problem: Buy items using k vouchers (50% off) to minimize cost.
Approach: Greedy + Sorting.
LeetCode Link: Minimum Cost to Buy Items
Tree-Based Problems (21–30)
21–25: Use Euler Tour, Binary Lifting, or Heavy-Light Decomposition.
LeetCode Links:
26–30: HLD or BFS/DFS for path queries.
GFG Links:
Miscellaneous Problems (31–43)
Energy Drain (31): Greedy with priority on high-energy exercises.
Array Transformation (32): Segment Tree with lazy updates.
Good Subarray Sum (33): Sliding Window + Hash Map.
Oil Tank (34): Prefix sum + Binary Search.
Enemy Army (35): BFS/DP for minimum steps.
Grid Invasion (36): Multi-source BFS.
For exact matches, search LeetCode/GfG using keywords like:
"Subarray with distinct elements ≤ k" (Problem 33).
"Binary Tree Cameras" (variant for Problem 29).