Categorised Ques on Bank (200 Ques ons)

1. Arrays & Searching

 Easy

1. Find missing number in 1…n

2. Find duplicate number

3. Rotate array by k

4. Majority element

5. Kadane’s algorithm

6. Equilibrium index

7. Subarray with given sum

8. Two-sum problem

9. Pythagorean triplet in array

10. Rearrange +ve/-ve alternately

11. Check if array is sorted and rotated

12. Find 2nd largest element

13. Move zeros to end

14. Remove duplicates from sorted array

15. Merge sorted arrays

16. Intersec on of two arrays

17. Union of arrays

18. Frequency count of elements

19. Check palindrome array

20. Find leader elements

21. Find smallest element in rotated sorted array

22. Find peak element

23. Binary search recursive

24. Square root of a number (binary search)

25. Count occurrences in sorted array

26. Find missing + repea ng number

public class ArrayProblems {

// 1) Find missing number in 1…n

// One-line: Given array of size n-1 containing dis nct numbers from 1..n, find the missing number.

// Approach: Use sum formula (O(n) me, O(1) space).

public sta c int missingNumber(int[] a, int n) {

long sum = (long)n * (n + 1) / 2;

long s = 0;

for (int x : a) s += x;

return (int)(sum - s);

// 2) Find duplicate number

// One-line: Given array with n+1 integers where each is in 1..n, find a duplicate.

// Approach: Floyd's Tortoise and Hare (O(n) me, O(1) space).

public sta c int findDuplicate(int[] a) {

int tort = a[0], hare = a[0];

do { tort = a[tort]; hare = a[a[hare]]; } while (tort != hare);

tort = a[0];

while (tort != hare) { tort = a[tort]; hare = a[hare]; }

return tort;

// 3) Rotate array by k
// One-line: Rotate array right by k posi ons (in-place).

// Approach: Reverse trick (O(n), O(1)).

public sta c void rotate(int[] a, int k) {

int n = [Link];

k %= n;

if (k < 0) k += n;
 reverse(a, 0, n-1);

reverse(a, 0, k-1);

reverse(a, k, n-1);

private sta c void reverse(int[] a, int i, int j) {

while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; }

// 4) Majority element
// One-line: Find element that appears > n/2 mes, if any.

// Approach: Boyer–Moore majority vote (O(n), O(1)).

public sta c int majorityElement(int[] a) {

int cand = 0, count = 0;

for (int x : a) {

if (count == 0) { cand = x; count = 1; }

else if (x == cand) count++;

else count--;

// if verifica on needed, iterate to check occurrence; we return candidate.

return cand;

// 5) Kadane’s algorithm
// One-line: Maximum subarray sum (con guous).

// Approach: Kadane (O(n), O(1)).

public sta c int kadane(int[] a) {

int maxSoFar = Integer.MIN_VALUE, maxEnding = 0;

for (int x : a) {

maxEnding = [Link](x, maxEnding + x);

maxSoFar = [Link](maxSoFar, maxEnding);

 }

return maxSoFar;

// 6) Equilibrium index
// One-line: Find an index where le sum equals right sum.

// Approach: Total sum then scan (O(n), O(1)).

public sta c int equilibriumIndex(int[] a) {

long total = 0;

for (int x : a) total += x;

long le = 0;

for (int i = 0; i < [Link]; i++) {

total -= a[i];

if (le == total) return i;

le += a[i];

return -1; // none

// 7) Subarray with given sum (non-nega ve numbers)

// One-line: Find any con guous subarray whose sum equals target (non-nega ve array).

// Approach: Sliding window (O(n), O(1)).

public sta c int[] subarrayWithGivenSum(int[] a, int target) {

int l = 0; long cur = 0;

for (int r = 0; r < [Link]; r++) {

cur += a[r];

while (cur > target && l <= r) cur -= a[l++];

if (cur == target) return new int[]{l, r}; // inclusive indices

return null;

}
// 8) Two-sum problem
// One-line: Return indices (or values) of two numbers that add to target.

// Approach: HashMap for values -> index (O(n), O(n)).

public sta c int[] twoSum(int[] a, int target) {

java.u [Link]<Integer,Integer> m = new java.u [Link]<>();

for (int i = 0; i < [Link]; i++) {

int need = target - a[i];

if ([Link](need)) return new int[]{[Link](need), i};

[Link](a[i], i);

return null;

// 9) Pythagorean triplet in array

// One-line: Check if there exist a,b,c such that a^2 + b^2 = c^2.

// Approach: Square and sort, two-pointer for each c (O(n^2), O(1) extra).

public sta c boolean hasPythagoreanTriplet(int[] a) {

int n = [Link];

long[] sq = new long[n];

for (int i = 0; i < n; i++) sq[i] = 1L * a[i] * a[i];

java.u [Link](sq);

for (int c = n-1; c >= 2; c--) {

int l = 0, r = c - 1;

while (l < r) {

long s = sq[l] + sq[r];

if (s == sq[c]) return true;

if (s < sq[c]) l++; else r--;

return false;
 }

// 10) Rearrange +ve/-ve alternately

// One-line: Rearrange array so posi ve and nega ve numbers alternate (rela ve order not
required).

// Approach: Par on then interleave (O(n), O(1) extra).

public sta c void rearrangePosNeg(int[] a) {

int n = [Link];

int i = 0, j = n - 1;

while (i < j) {

while (i < n && a[i] < 0) i++;

while (j >= 0 && a[j] >= 0) j--;

if (i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

// i is first non-nega ve index

int pos = i, neg = 0;

while (pos < n && neg < pos && a[neg] < 0) {

int t = a[neg]; a[neg] = a[pos]; a[pos] = t;

neg += 2; pos++;

// 11) Check if array is sorted and rotated

// One-line: Check if array is a rota on of a non-decreasing sorted array.

// Approach: Count places where a[i] > a[i+1]; allow at most one (O(n), O(1)).

public sta c boolean isSortedAndRotated(int[] a) {

int n = [Link], count = 0;

for (int i = 0; i < n; i++) {

if (a[i] > a[(i+1)%n]) count++;

if (count > 1) return false;

}
 return true;

// 12) Find 2nd largest element

// One-line: Return second largest dis nct element (or Integer.MIN_VALUE if none).

// Approach: Single pass tracking max and second max (O(n), O(1)).

public sta c Integer secondLargest(int[] a) {

if ([Link] < 2) return null;

long max = Long.MIN_VALUE, second = Long.MIN_VALUE;

for (int x : a) {

if (x > max) { second = max; max = x; }

else if (x > second && x < max) second = x;

return (second == Long.MIN_VALUE) ? null : (int)second;

// 13) Move zeros to end

// One-line: Move all zeros to the end while preserving order of non-zeros.

// Approach: Two-pointer (O(n), O(1)).

public sta c void moveZerosToEnd(int[] a) {

int pos = 0;

for (int x : a) if (x != 0) a[pos++] = x;

while (pos < [Link]) a[pos++] = 0;

// 14) Remove duplicates from sorted array

// One-line: Given sorted array, remove duplicates in-place and return new length.

// Approach: Two-pointer (O(n), O(1)).

public sta c int removeDuplicatesSorted(int[] a) {

if ([Link] == 0) return 0;
 int idx = 0;

for (int i = 1; i < [Link]; i++) if (a[i] != a[idx]) a[++idx] = a[i];

return idx + 1;

// 15) Merge sorted arrays

// One-line: Merge two sorted arrays into a new sorted array.

// Approach: Two-pointer merge (O(n+m), O(n+m)).

public sta c int[] mergeSorted(int[] a, int[] b) {

int n = [Link], m = [Link], i = 0, j = 0, k = 0;

int[] res = new int[n + m];

while (i < n && j < m) res[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];

while (i < n) res[k++] = a[i++];

while (j < m) res[k++] = b[j++];

return res;

// 16) Intersec on of two arrays

// One-line: Return intersec on (unique values) of two arrays.

// Approach: HashSet (O(n+m), O(min(n,m))).

public sta c int[] intersec on(int[] a, int[] b) {

java.u [Link]<Integer> sa = new java.u [Link]<>();

for (int x : a) [Link](x);

java.u [Link]<Integer> inter = new java.u [Link]<>();

for (int x : b) if ([Link](x)) [Link](x);

int[] res = new int[[Link]()]; int i=0;

for (int x : inter) res[i++] = x;

return res;

}
// 17) Union of arrays
// One-line: Return union (unique values) of two arrays.

// Approach: HashSet (O(n+m)).

public sta c int[] union(int[] a, int[] b) {

java.u [Link]<Integer> s = new java.u [Link]<>();

for (int x : a) [Link](x);

for (int x : b) [Link](x);

int[] res = new int[[Link]()]; int i = 0;

for (int x : s) res[i++] = x;

return res;

// 18) Frequency count of elements

// One-line: Count frequency of each element (returns map).

// Approach: HashMap (O(n), O(n)).

public sta c java.u [Link]<Integer,Integer> frequencyCount(int[] a) {

java.u [Link]<Integer,Integer> m = new java.u [Link]<>();

for (int x : a) [Link](x, [Link](x,0)+1);

return m;

// 19) Check palindrome array

// One-line: Check if array reads same forwards and backwards.

// Approach: Two-pointer (O(n), O(1)).

public sta c boolean isPalindromeArray(int[] a) {

int i = 0, j = [Link] - 1;

while (i < j) if (a[i++] != a[j--]) return false;

return true;

}
// 20) Find leader elements
// One-line: Elements greater than all elements to their right (leaders).

// Approach: Scan from right keeping max (O(n), O(1) extra).

public sta c java.u [Link]<Integer> leaders(int[] a) {

java.u [Link]<Integer> res = new java.u [Link]<>();

int n = [Link];

int max = Integer.MIN_VALUE;

for (int i = n - 1; i >= 0; i--) {

if (a[i] > max) { [Link](0, a[i]); max = a[i]; }

return res;

// 21) Find smallest element in rotated sorted array

// One-line: Find minimum in rotated sorted array (no duplicates).

// Approach: Binary search (O(log n)).

public sta c int findMinInRotated(int[] a) {

int l = 0, r = [Link] - 1;

while (l < r) {

int m = l + (r - l) / 2;

if (a[m] > a[r]) l = m + 1;

else r = m;

return a[l];

// 22) Find peak element

// One-line: Find index of any peak (element >= neighbors).

// Approach: Binary search (O(log n)).

public sta c int findPeakElement(int[] a) {

 int l = 0, r = [Link] - 1;

while (l < r) {

int m = l + (r - l) / 2;

if (a[m] > a[m+1]) r = m;

else l = m + 1;

return l;

// 23) Binary search recursive

// One-line: Classic recursive binary search on sorted array.

// Approach: Divide and conquer (O(log n)).

public sta c int binarySearchRec(int[] a, int target) {

return bsHelper(a, 0, [Link] - 1, target);

private sta c int bsHelper(int[] a, int l, int r, int t) {

if (l > r) return -1;

int m = l + (r - l) / 2;

if (a[m] == t) return m;

if (a[m] < t) return bsHelper(a, m + 1, r, t);

else return bsHelper(a, l, m - 1, t);

// 24) Square root of a number (binary search)

// One-line: Integer square root floor(n) using binary search.

// Approach: Binary search on range (O(log n)).

public sta c long integerSqrt(long x) {

if (x < 2) return x;

long l = 1, r = x/2, ans = 1;

while (l <= r) {

long m = l + (r - l) / 2;
 if (m <= x / m) { ans = m; l = m + 1; }

else r = m - 1;

return ans;

// 25) Count occurrences in sorted array

// One-line: Count how many mes target appears in sorted array.

// Approach: Two binary searches for le and right bound (O(log n)).

public sta c int countOccurrencesSorted(int[] a, int target) {

int le = firstGreaterEqual(a, target);

int right = firstGreaterEqual(a, target + 1);

return right - le ;

private sta c int firstGreaterEqual(int[] a, int target) {

int l = 0, r = [Link];

while (l < r) {

int m = l + (r - l) / 2;

if (a[m] < target) l = m + 1; else r = m;

return l;

// 26) Find missing + repea ng number

// One-line: Given array of size n with numbers 1..n where one missing and one repea ng, find
both.

// Approach: Use XOR or mathema cal formulas (O(n), O(1)).

public sta c int[] findMissingAndRepea ng(int[] a) {

int n = [Link];

long sumN = (long)n*(n+1)/2;

long sumSqN = (long)n*(n+1)*(2L*n+1)/6;

 long s = 0, sq = 0;

for (int x : a) { s += x; sq += 1L*x*x; }

long diff = sumN - s; // missing - repea ng = diff

long sqDiff = sumSqN - sq; // missing^2 - repea ng^2 = sqDiff

long sumMR = sqDiff / diff; // missing + repea ng

long missing = (diff + sumMR) / 2;

long repea ng = sumMR - missing;

return new int[]{(int)missing, (int)repea ng};

 Medium

1. Search in rotated sorted array

2. Next greater element

3. Trapping rainwater

4. Container with most water

5. Largest rectangle in histogram

6. Longest increasing subsequence

7. 3Sum problem

8. 3Sum closest

9. 4Sum problem

10. Par on equal subset sum

11. Count inversions in array

12. Minimum jumps to end

13. Smallest missing posi ve

14. Longest consecu ve sequence

15. Subarray with XOR = k

16. Maximum product subarray

17. Allocate minimum pages

18. Merge intervals

19. Mee ng rooms problem

20. Stock buy & sell (I, II, III, cooldown)

21. Longest subarray with sum K

22. Maximum circular subarray sum

23. Sliding window maximum

24. Median of data stream

import java.u l.*;

/**

* AdvancedArrayProblems

* This file implements 24 array/sequence problems o en asked in interviews.

* Each method is self-contained, op mized, and contains step-by-step comments

* explaining the approach, complexity, and corner-cases.

* Usage: copy this file into [Link] and call sta c methods

* from your tests or main method.

* I tried to keep signatures clear and return meaningful types (indexes, values,

* lists, or counts) depending on the problem. For problems that have mul ple

* variants (e.g., mee ng rooms), I included commonly-used helper methods.

*/

public class AdvancedArrayProblems {

// ------------------------------

// 1) Search in Rotated Sorted Array

// ------------------------------

/**

* Problem: Given a sorted array that has been rotated at some pivot, search for target and

* return its index or -1 if not present. Assumes no duplicate values.

* Approach: Modified binary search using the observa on that one half is always sorted.

* Time: O(log n), Space: O(1)

*/

public sta c int searchInRotated(int[] nums, int target) {

int l = 0, r = [Link] - 1;

while (l <= r) {

int m = l + (r - l) / 2;

if (nums[m] == target) return m;

// If le half is sorted

if (nums[l] <= nums[m]) {

// Check if target lies in le half

if (nums[l] <= target && target < nums[m]) r = m - 1;

else l = m + 1;

} else { // right half is sorted

if (nums[m] < target && target <= nums[r]) l = m + 1;

else r = m - 1;

return -1;

// ------------------------------

// 2) Next Greater Element (for each element)

// ------------------------------

/**

* Problem: For each element in array, find the next greater element to its right. If none, -1.

* Approach: Use a monotonic decreasing stack that stores indices. O(n) me, O(n) space.

*/

public sta c int[] nextGreaterElements(int[] nums) {

int n = [Link];

int[] res = new int[n];

 Arrays.fill(res, -1);

Deque<Integer> st = new ArrayDeque<>(); // store indices

for (int i = 0; i < n; i++) {

// pop smaller elements since current is their next greater

while (![Link]() && nums[i] > nums[[Link]()]) {

res[[Link]()] = nums[i];

[Link](i);

// remaining indices have no greater element -> -1 already set

return res;

// ------------------------------

// 3) Trapping Rainwater
// ------------------------------

/**

* Problem: Given heights array where each bar width=1, compute trapped water.

* Approach: Two-pointer technique tracking le Max and rightMax. O(n), O(1).

*/

public sta c int trapRainWater(int[] height) {

int l = 0, r = [Link] - 1;

int le Max = 0, rightMax = 0;

int ans = 0;

while (l <= r) {

if (height[l] <= height[r]) {

// le side is limi ng

if (height[l] >= le Max) le Max = height[l];

else ans += le Max - height[l];

l++;

} else {
 if (height[r] >= rightMax) rightMax = height[r];

else ans += rightMax - height[r];

r--;

return ans;

// ------------------------------

// 4) Container With Most Water

// ------------------------------

/**

* Problem: Given heights represen ng ver cal lines, choose two that contain most water.

* Approach: Two-pointer shrinking the smaller side, O(n), O(1).

*/

public sta c int maxAreaContainer(int[] height) {

int l = 0, r = [Link] - 1;

int best = 0;

while (l < r) {

int h = [Link](height[l], height[r]);

int area = h * (r - l);

if (area > best) best = area;

// move the smaller side inward to try increase height

if (height[l] < height[r]) l++; else r--;

return best;

// ------------------------------

// 5) Largest Rectangle in Histogram

// ------------------------------
/**

* Problem: Given heights of histogram bars, find largest rectangular area.

* Approach: Use stack of indices of increasing heights; compute area when popping.

* Time: O(n), Space: O(n)

*/

public sta c int largestRectangleArea(int[] heights) {

int n = [Link];

Deque<Integer> st = new ArrayDeque<>();

int maxArea = 0;

for (int i = 0; i <= n; i++) {

// treat sen nel height 0 at end to flush stack

int h = (i == n) ? 0 : heights[i];

while (![Link]() && h < heights[[Link]()]) {

int height = heights[[Link]()];

int le = [Link]() ? 0 : [Link]() + 1;

int width = i - le ; // current i is the right boundary (exclusive)

maxArea = [Link](maxArea, height * width);

[Link](i);

return maxArea;

// ------------------------------

// 6) Longest Increasing Subsequence (length) - O(n log n)

// ------------------------------

/**

* Problem: Length of longest strictly increasing subsequence.

* Approach: Pa ence sor ng (tails array + binary search). O(n log n).

*/

public sta c int lengthOfLIS(int[] nums) {

 if ([Link] == 0) return 0;

int[] tails = new int[[Link]];

int size = 0;

for (int x : nums) {

// binary search for inser on posi on

int i = [Link](tails, 0, size, x);

if (i < 0) i = -(i + 1);

tails[i] = x; // replace or extend

if (i == size) size++;

return size;

// ------------------------------

// 7) 3Sum Problem (unique triplets that sum to 0)

// ------------------------------

/**

* Problem: Find all unique triplets [a,b,c] with a+b+c == 0.

* Approach: Sort and use two pointers; deduplicate by skipping equal neighbors. O(n^2).

*/

public sta c List<List<Integer>> threeSumZero(int[] nums) {

[Link](nums);

List<List<Integer>> res = new ArrayList<>();

int n = [Link];

for (int i = 0; i < n - 2; i++) {

if (i > 0 && nums[i] == nums[i - 1]) con nue; // skip duplicates

int target = -nums[i];

int l = i + 1, r = n - 1;

while (l < r) {

int sum = nums[l] + nums[r];

if (sum == target) {
 [Link]([Link](nums[i], nums[l], nums[r]));

// skip duplicates

while (l < r && nums[l] == nums[l + 1]) l++;

while (l < r && nums[r] == nums[r - 1]) r--;

l++; r--;

} else if (sum < target) l++; else r--;

return res;

// ------------------------------

// 8) 3Sum Closest
// ------------------------------

/**

* Problem: Find sum of triplet closest to target and return that sum.

* Approach: Sort + two pointers, track closest difference. O(n^2).

*/

public sta c int threeSumClosest(int[] nums, int target) {

[Link](nums);

int n = [Link];

int bestSum = nums[0] + nums[1] + nums[2];

for (int i = 0; i < n - 2; i++) {

int l = i + 1, r = n - 1;

while (l < r) {

int sum = nums[i] + nums[l] + nums[r];

if ([Link](sum - target) < [Link](bestSum - target)) bestSum = sum;

if (sum == target) return sum; // perfect

if (sum < target) l++; else r--;

}
 return bestSum;

// ------------------------------

// 9) 4Sum Problem
// ------------------------------

/**

* Problem: Find all unique quadruplets that sum to target.

* Approach: Sort + two nested loops + two pointers for the remaining two; deduplicate.

* Time: O(n^3), Space: O(1) extra (besides output).

*/

public sta c List<List<Integer>> fourSum(int[] nums, int target) {

[Link](nums);

List<List<Integer>> res = new ArrayList<>();

int n = [Link];

for (int i = 0; i < n - 3; i++) {

if (i > 0 && nums[i] == nums[i - 1]) con nue;

for (int j = i + 1; j < n - 2; j++) {

if (j > i + 1 && nums[j] == nums[j - 1]) con nue;

int l = j + 1, r = n - 1;

long rem = (long)target - nums[i] - nums[j];

while (l < r) {

long sum2 = nums[l] + nums[r];

if (sum2 == rem) {

[Link]([Link](nums[i], nums[j], nums[l], nums[r]));

while (l < r && nums[l] == nums[l + 1]) l++;

while (l < r && nums[r] == nums[r - 1]) r--;

l++; r--;

} else if (sum2 < rem) l++; else r--;

}
 }

return res;

// ------------------------------

// 10) Par on Equal Subset Sum

// ------------------------------

/**

* Problem: Check if array can be par oned into two subsets with equal sum.

* Approach: classic subset sum dynamic programming. Use boolean DP or BitSet for memory

* efficiency.

* Time: O(n * sum), Space: O(sum) or use BitSet which is faster in prac ce.

*/

public sta c boolean canPar onEqualSubset(int[] nums) {

int sum = 0;

for (int x : nums) sum += x;

if ((sum & 1) == 1) return false; // odd cannot par on equally

int target = sum / 2;

// BitSet op miza on: dp bit i is true if sum i is achievable

BitSet bits = new BitSet(target + 1);

[Link](0);

for (int x : nums) {

// shi bits le by x: achievable sums increase

BitSet shi ed = [Link](0, [Link](target + 1, [Link]()));

shi ed = shi Le (bits, x, target);

[Link](shi ed);

if ([Link](target)) return true;

return [Link](target);

// helper to shi BitSet le by k limited to maxIndex

private sta c BitSet shi Le (BitSet bs, int k, int maxIndex) {

BitSet res = new BitSet(maxIndex + 1);

for (int i = [Link](0); i >= 0 && i + k <= maxIndex; i = [Link](i + 1)) {

[Link](i + k);

return res;

// ------------------------------

// 11) Count Inversions in Array

// ------------------------------

/**

* Problem: Number of pairs (i,j) such that i<j and a[i] > a[j].

* Approach: Modified merge sort that counts inversions when merging two halves.

* Time: O(n log n), Space: O(n)

*/

public sta c long countInversions(int[] arr) {

int n = [Link];

int[] temp = new int[n];

return mergeSortCount(arr, temp, 0, n - 1);

private sta c long mergeSortCount(int[] a, int[] tmp, int l, int r) {

if (l >= r) return 0;

int m = l + (r - l) / 2;

long inv = mergeSortCount(a, tmp, l, m) + mergeSortCount(a, tmp, m + 1, r);

int i = l, j = m + 1, k = l;

while (i <= m && j <= r) {

if (a[i] <= a[j]) tmp[k++] = a[i++];

else {

// a[i] > a[j] and all a[i..m] will be > a[j]

tmp[k++] = a[j++];
 inv += (m - i + 1);

while (i <= m) tmp[k++] = a[i++];

while (j <= r) tmp[k++] = a[j++];

[Link](tmp, l, a, l, r - l + 1);

return inv;

// ------------------------------

// 12) Minimum Jumps to End (Jump Game II)

// ------------------------------

/**

* Problem: Given array where each element is max jump length, return minimum jumps to reach
end.

* Approach: Greedy BFS-like using current reach and next reach. O(n), O(1).

*/

public sta c int minJumpsToEnd(int[] nums) {

if ([Link] <= 1) return 0;

int jumps = 0;

int currentEnd = 0;

int farthest = 0;

for (int i = 0; i < [Link] - 1; i++) {

farthest = [Link](farthest, i + nums[i]);

if (i == currentEnd) {

jumps++;

currentEnd = farthest;

if (currentEnd >= [Link] - 1) break;

return currentEnd >= [Link] - 1 ? jumps : -1; // -1 if cannot reach

 }

// ------------------------------

// 13) Smallest Missing Posi ve

// ------------------------------
/**

* Problem: Find smallest missing posi ve integer in unsorted array in O(n) me and O(1) space.

* Approach: Place each number x at index x-1 by swapping; then first place where arr[i]!=i+1 is
answer.

*/

public sta c int firstMissingPosi ve(int[] nums) {

int n = [Link];

for (int i = 0; i < n; i++) {

while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {

// swap nums[i] and nums[nums[i]-1]

int tmp = nums[nums[i] - 1];

nums[nums[i] - 1] = nums[i];

nums[i] = tmp;

for (int i = 0; i < n; i++) if (nums[i] != i + 1) return i + 1;

return n + 1;

// ------------------------------

// 14) Longest Consecu ve Sequence

// ------------------------------

/**

* Problem: Given unsorted array, find length of longest sequence of consecu ve integers.

* Approach: Use HashSet to find starts of sequences and extend. O(n) average.

*/
public sta c int longestConsecu ve(int[] nums) {

Set<Integer> s = new HashSet<>();

for (int x : nums) [Link](x);

int best = 0;

for (int x : s) {

if () { // start of sequence

int cur = x, len = 1;

while ([Link](cur + 1)) { cur++; len++; }

best = [Link](best, len);

return best;

// ------------------------------

// 15) Subarray with XOR = k (count of subarrays)

// ------------------------------

/**

* Problem: Count number of subarrays with XOR equal to k.

* Approach: Prefix XOR + HashMap coun ng frequencies of seen XORs. O(n).

*/

public sta c int countSubarraysWithXor(int[] arr, int k) {

Map<Integer, Integer> freq = new HashMap<>();

int prefix = 0, count = 0;

[Link](0, 1); // empty prefix

for (int x : arr) {

prefix ^= x;

// we need prefix ^ some = k => some = prefix ^ k

int need = prefix ^ k;

count += [Link](need, 0);

[Link](prefix, [Link](prefix, 0) + 1);

 }

return count;

// ------------------------------

// 16) Maximum Product Subarray

// ------------------------------

/**

* Problem: Maximum product of a con guous subarray.

* Approach: Track maxEndingHere and minEndingHere to handle sign flips by nega ve numbers.

* Time: O(n)

*/

public sta c long maxProductSubarray(int[] nums) {

long maxSoFar = Long.MIN_VALUE;

long maxEnding = 1, minEnding = 1;

boolean started = false;

for (int x : nums) {

if (!started) {

maxEnding = minEnding = x;

maxSoFar = x;

started = true;

con nue;

if (x == 0) {

maxEnding = 1; minEnding = 1;

maxSoFar = [Link](maxSoFar, 0L);

con nue;

long tempMax = [Link](x, [Link](maxEnding * x, minEnding * x));

long tempMin = [Link](x, [Link](maxEnding * x, minEnding * x));

maxEnding = tempMax;
 minEnding = tempMin;

maxSoFar = [Link](maxSoFar, maxEnding);

return maxSoFar;

// ------------------------------

// 17) Allocate Minimum Pages (Book Alloca on)

// ------------------------------

/**

* Problem: Given array of pages per book and m students, assign con guous books

* to students minimizing the maximum pages assigned to any student. Return that min max.

* Approach: Binary search on answer (min possible max pages) and greedily check feasibility.

*/

public sta c long allocateMinimumPages(int[] pages, int students) {

if (students > [Link]) return -1; // each student must get at least one book

long l = 0, r = 0;

for (int p : pages) { l = [Link](l, p); r += p; }

long ans = r;

while (l <= r) {

long mid = l + (r - l) / 2; // candidate maximum pages

if (canAllocate(pages, students, mid)) { ans = mid; r = mid - 1; }

else l = mid + 1;

return ans;

private sta c boolean canAllocate(int[] pages, int students, long maxPages) {

int count = 1; long sum = 0;

for (int p : pages) {

if (sum + p <= maxPages) sum += p;

else { count++; sum = p; if (count > students) return false; }

 }

return true;

// ------------------------------

// 18) Merge Intervals

// ------------------------------

/**

* Problem: Given list of intervals [start,end], merge overlapping intervals and return merged list.

* Approach: Sort by start then iterate merging when overlapping. O(n log n).

*/

public sta c List<int[]> mergeIntervals(int[][] intervals) {

List<int[]> res = new ArrayList<>();

if (intervals == null || [Link] == 0) return res;

[Link](intervals, [Link](a -> a[0]));

int[] cur = intervals[0].clone();

for (int i = 1; i < [Link]; i++) {

if (intervals[i][0] <= cur[1]) {

// overlap -> extend end

cur[1] = [Link](cur[1], intervals[i][1]);

} else {

[Link](cur);

cur = intervals[i].clone();

[Link](cur);

return res;

// ------------------------------

// 19) Mee ng Rooms (can a end all? and min rooms required)
// ------------------------------

/**

* Problem A: Determine if a person can a end all mee ngs (no overlaps).

* Problem B: Minimum number of mee ng rooms required (max overlapping mee ngs).

*/

public sta c boolean canA endAllMee ngs(int[][] intervals) {

if (intervals == null) return true;

[Link](intervals, [Link](a -> a[0]));

for (int i = 1; i < [Link]; i++) {

if (intervals[i][0] < intervals[i - 1][1]) return false;

return true;

public sta c int minMee ngRooms(int[][] intervals) {

if (intervals == null || [Link] == 0) return 0;

[Link](intervals, [Link](a -> a[0]));

PriorityQueue<Integer> pq = new PriorityQueue<>(); // track end mes

[Link](intervals[0][1]);

for (int i = 1; i < [Link]; i++) {

if (intervals[i][0] >= [Link]()) {

// reuse room

[Link]();

[Link](intervals[i][1]);

return [Link]();

// ------------------------------

// 20) Stock Buy & Sell Variants

// ------------------------------
/**

* I: Best me to buy and sell (one transac on) -> max profit

*/

public sta c int maxProfitSingleTransac on(int[] prices) {

int minPrice = Integer.MAX_VALUE, profit = 0;

for (int p : prices) {

minPrice = [Link](minPrice, p);

profit = [Link](profit, p - minPrice);

return profit;

/**

* II: Unlimited transac ons -> sum of all increasing slopes

*/

public sta c int maxProfitUnlimited(int[] prices) {

int profit = 0;

for (int i = 1; i < [Link]; i++) if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];

return profit;

/**

* III: At most two transac ons -> DP with 4 states or le /right pass.

*/

public sta c int maxProfitTwoTransac ons(int[] prices) {

if ([Link] == 0) return 0;

int n = [Link];

int[] le = new int[n]; // max profit up to i

int minP = prices[0];

for (int i = 1; i < n; i++) {

minP = [Link](minP, prices[i]);

le [i] = [Link](le [i - 1], prices[i] - minP);

}
 int[] right = new int[n + 1]; // max profit from i to end

int maxP = prices[n - 1];

for (int i = n - 2; i >= 0; i--) {

maxP = [Link](maxP, prices[i]);

right[i] = [Link](right[i + 1], maxP - prices[i]);

int best = 0;

for (int i = 0; i < n; i++) best = [Link](best, le [i] + right[i + 1]);

best = [Link](best, le [n - 1]);

return best;

/**

* Cooldown (infinite transac ons, but a er selling you must cooldown one day)

* Approach: DP keeping states: hold, sold, rest. O(n)

*/

public sta c int maxProfitWithCooldown(int[] prices) {

if ([Link] == 0) return 0;

int n = [Link];

long hold = -prices[0]; // max profit when holding stock

long sold = 0; // max profit when just sold

long rest = 0; // max profit when res ng

for (int i = 1; i < n; i++) {

long prevSold = sold;

sold = hold + prices[i]; // sell today

hold = [Link](hold, rest - prices[i]); // buy or keep

rest = [Link](rest, prevSold); // either rest or cooldown finished

return (int)[Link](sold, rest);

// ------------------------------
 // 21) Longest Subarray with Sum K (may contain nega ve numbers)
// ------------------------------

/**

* Problem: Find the length of the longest subarray with sum equal to K. Works with nega ves.

* Approach: Prefix sum + hashmap storing earliest index each prefix sum appeared.

*/

public sta c int longestSubarraySumK(int[] nums, int k) {

Map<Integer, Integer> firstIndex = new HashMap<>();

int prefix = 0, best = 0;

fi[Link](0, -1); // prefix sum 0 at index -1

for (int i = 0; i < [Link]; i++) {

prefix += nums[i];

if (fi[Link](prefix - k)) {

best = [Link](best, i - fi[Link](prefix - k));

// store earliest index for this prefix only

fi[Link](prefix, i);

return best;

// ------------------------------

// 22) Maximum Circular Subarray Sum

// ------------------------------

/**

* Problem: Max subarray sum of circular array.

* Approach: Either normal Kadane's maximum subarray or take total - minimum-subarray (Kadane
on inverted array).

* Handle case where all are nega ve separately.

*/

public sta c int maxSubarraySumCircular(int[] nums) {

 // normal Kadane

int maxEnding = nums[0], maxSoFar = nums[0];

int minEnding = nums[0], minSoFar = nums[0];

int total = nums[0];

for (int i = 1; i < [Link]; i++) {

int x = nums[i];

maxEnding = [Link](x, maxEnding + x);

maxSoFar = [Link](maxSoFar, maxEnding);

minEnding = [Link](x, minEnding + x);

minSoFar = [Link](minSoFar, minEnding);

total += x;

if (maxSoFar < 0) return maxSoFar; // all nega ve

return [Link](maxSoFar, total - minSoFar);

// ------------------------------

// 23) Sliding Window Maximum

// ------------------------------

/**

* Problem: Given array and window size k, return array of maximums for each window.

* Approach: Deque maintaining indices of useful elements (decreasing values). O(n)

*/

public sta c int[] slidingWindowMax(int[] nums, int k) {

if (k == 0) return new int[0];

int n = [Link];

int[] ans = new int[n - k + 1];

Deque<Integer> dq = new ArrayDeque<>(); // store indices of decreasing values

for (int i = 0; i < n; i++) {

// pop indices out of window

while (![Link]() && [Link]() <= i - k) [Link]();

 // remove smaller values; they won't be needed

while (![Link]() && nums[[Link]()] < nums[i]) [Link]();

[Link](i);

if (i >= k - 1) ans[i - k + 1] = nums[[Link]()];

return ans;

// ------------------------------

// 24) Median of Data Stream

// ------------------------------

/**

* Problem: Maintain a data structure to add numbers and return median at any me.

* Approach: Two heaps: max-heap for lower half, min-heap for upper half.

*/

public sta c class MedianFinder {

private PriorityQueue<Integer> low; // max-heap

private PriorityQueue<Integer> high; // min-heap

public MedianFinder() {

low = new PriorityQueue<>(Collec [Link]());

high = new PriorityQueue<>();

public void addNum(int num) {

// keep sizes balanced: [Link]() == [Link]() or [Link]() == [Link]()+1

if ([Link]() || num <= [Link]()) [Link](num);

else [Link](num);

// rebalance

if ([Link]() - [Link]() >= 2) [Link]([Link]());

else if ([Link]() > [Link]()) [Link]([Link]());

public double findMedian() {

 if ([Link]() == [Link]()) return ([Link]() + [Link]()) / 2.0;

return [Link]();

// ------------------------------

// (Op onal) A small main to demonstrate a few methods (uncomment to

run tests)
// ------------------------------

public sta c void main(String[] args) {

// Example quick checks (uncomment to run)

// int[] arr = {4,5,6,7,0,1,2}; [Link](searchInRotated(arr, 0));

// int[] heights = {0,1,0,2,1,0,1,3,2,1,2,1}; [Link](trapRainWater(heights));

// int[] hs = {2,1,5,6,2,3}; [Link](largestRectangleArea(hs));

// int[] a = {2, -1, 2, 3, -5, 4}; [Link](maxProductSubarray(a));

 Hard

o Median of two sorted arrays

o Maximum XOR of two numbers in array

o Painter par on problem

o Minimum swaps to sort array

o Range sum queries (Fenwick tree)

o Range minimum queries (Segment tree)

o Burst balloons problem

o Merge stones problem

Median of two sorted arrays

One-line: Find the median of two sorted arrays in O(log(min(m,n))) me without merging them.

// [Link]

public class MedianTwoSortedArrays {

// Returns median of two sorted arrays

public sta c double findMedian(int[] A, int[] B) {

if ([Link] > [Link]) return findMedian(B, A); // ensure A is smaller

int m = [Link], n = [Link];

int half = (m + n + 1) / 2;

int lo = 0, hi = m;

while (lo <= hi) {

int i = (lo + hi) / 2; // par on A

int j = half - i; // par on B

int Ale = (i == 0) ? Integer.MIN_VALUE : A[i - 1];

int Aright = (i == m) ? Integer.MAX_VALUE : A[i];

int Ble = (j == 0) ? Integer.MIN_VALUE : B[j - 1];

int Bright = (j == n) ? Integer.MAX_VALUE : B[j];

if (Ale <= Bright && Ble <= Aright) {

if ((m + n) % 2 == 1) return [Link](Ale , Ble );

return ([Link](Ale , Ble ) + [Link](Aright, Bright)) / 2.0;

} else if (Ale > Bright) {

hi = i - 1;

} else {

lo = i + 1;

throw new IllegalArgumentExcep on("Input arrays are not sorted properly.");

// quick test

public sta c void main(String[] args) {

 int[] A = {1, 3};

int[] B = {2};

[Link](findMedian(A, B)); // 2.0

Complexity: O(log(min(m,n))) me, O(1) space.

Maximum XOR of two numbers in array

One-line: Find the maximum XOR ai ^ aj over all pairs using a bitwise trie (prefix tree).

// [Link]

import java.u l.*;

public class MaxXORPair {

sta c class TrieNode {

TrieNode[] next = new TrieNode[2];

public sta c int findMaximumXOR(int[] nums) {

TrieNode root = new TrieNode();

// insert number into trie

for (int num : nums) {

TrieNode node = root;

for (int k = 31; k >= 0; k--) {

int bit = (num >> k) & 1;

if ([Link][bit] == null) [Link][bit] = new TrieNode();

node = [Link][bit];

int max = 0;

for (int num : nums) {

TrieNode node = root;

 int cur = 0;

for (int k = 31; k >= 0; k--) {

int bit = (num >> k) & 1;

int want = 1 - bit;

if ([Link][want] != null) {

cur |= (1 << k);

node = [Link][want];

} else {

node = [Link][bit];

max = [Link](max, cur);

return max;

public sta c void main(String[] args) {

int[] arr = {3, 10, 5, 25, 2, 8};

[Link](findMaximumXOR(arr)); // 28 (5 ^ 25)

Complexity: O(n * W) me where W=32 (bits), space O(n*W).

Painter Par on Problem

One-line: Minimize the maximum me taken by painters when boards are par oned con guously;
solve with binary search.

// PainterPar [Link]

public class PainterPar on {

// Given board lengths and painters p, me per unit ' meUnit'

public sta c long minTime(int[] boards, int painters, long meUnit) {

long lo = 0, hi = 0;
 for (int b : boards) { hi += b; lo = [Link](lo, b); }

// binary search on maximum sum assigned to a painter

long ans = hi;

while (lo <= hi) {

long mid = (lo + hi) / 2;

if (canPaint(boards, painters, mid)) {

ans = mid;

hi = mid - 1;

} else lo = mid + 1;

return ans * meUnit;

private sta c boolean canPaint(int[] boards, int painters, long maxSum) {

int required = 1;

long cur = 0;

for (int b : boards) {

if (cur + b <= maxSum) cur += b;

else {

required++;

cur = b;

if (required > painters) return false;

return true;

public sta c void main(String[] args) {

int[] boards = {10, 20, 30, 40};

int painters = 2;

long meUnit = 1; // unit me per length

 [Link](minTime(boards, painters, meUnit)); // 60

Complexity: O(n * log(sum)) me, O(1) space.

Minimum swaps to sort array

One-line: Minimum number of swaps to sort an array (all elements dis nct) — count cycles in the
permuta on.

// [Link]

import java.u l.*;

public class MinSwapsToSort {

public sta c int minSwaps(int[] arr) {

int n = [Link];

int[][] paired = new int[n][2];

for (int i = 0; i < n; i++) { paired[i][0] = arr[i]; paired[i][1] = i; }

[Link](paired, [Link](a -> a[0]));

boolean[] visited = new boolean[n];

int swaps = 0;

for (int i = 0; i < n; i++) {

if (visited[i] || paired[i][1] == i) con nue;

int cycleSize = 0;

int j = i;

while (!visited[j]) {

visited[j] = true;

j = paired[j][1];

cycleSize++;

if (cycleSize > 0) swaps += (cycleSize - 1);

return swaps;
 }

public sta c void main(String[] args) {

int[] arr = {4, 3, 2, 1};

[Link](minSwaps(arr)); // 2

Complexity: O(n log n) me (due to sort), O(n) space.

Range sum queries (Fenwick tree / BIT)

One-line: Support point updates and prefix/range sum queries in O(log n) with a Binary Indexed Tree.

// [Link]

public class FenwickTree {

private final int n;

private final long[] bit;

public FenwickTree(int size) {

this.n = size;

[Link] = new long[size + 1];

// add val at index (1-based)

public void add(int idx, long val) {

for (; idx <= n; idx += idx & -idx) bit[idx] += val;

// prefix sum [1..idx]

public long sum(int idx) {

long res = 0;

for (; idx > 0; idx -= idx & -idx) res += bit[idx];

return res;
 }

// range sum [l..r], 1-based

public long rangeSum(int l, int r) {

return sum(r) - sum(l - 1);

public sta c void main(String[] args) {

FenwickTree = new FenwickTree(5);

.add(1, 5);

.add(2, 3);

.add(4, 7);

[Link]( .rangeSum(1, 4)); // 15

Complexity: O(log n) per update/query, O(n) space.

Range minimum queries (Segment tree)

One-line: Build a segment tree to answer range minimum queries and point updates in O(log n).

// [Link]

public class SegmentTreeRMQ {

private final int n;

private final int[] tree;

public SegmentTreeRMQ(int[] arr) {

this.n = [Link];

tree = new int[4 * n];

build(arr, 1, 0, n - 1);

private void build(int[] a, int node, int l, int r) {

 if (l == r) { tree[node] = a[l]; return; }

int mid = (l + r) / 2;

build(a, node * 2, l, mid);

build(a, node * 2 + 1, mid + 1, r);

tree[node] = [Link](tree[node * 2], tree[node * 2 + 1]);

public void update(int idx, int val) { update(1, 0, n - 1, idx, val); }

private void update(int node, int l, int r, int idx, int val) {

if (l == r) { tree[node] = val; return; }

int mid = (l + r) / 2;

if (idx <= mid) update(node * 2, l, mid, idx, val);

else update(node * 2 + 1, mid + 1, r, idx, val);

tree[node] = [Link](tree[node * 2], tree[node * 2 + 1]);

public int rangeMin(int ql, int qr) { return rangeMin(1, 0, n - 1, ql, qr); }

private int rangeMin(int node, int l, int r, int ql, int qr) {

if (qr < l || r < ql) return Integer.MAX_VALUE;

if (ql <= l && r <= qr) return tree[node];

int mid = (l + r) / 2;

return [Link](rangeMin(node * 2, l, mid, ql, qr),

rangeMin(node * 2 + 1, mid + 1, r, ql, qr));

public sta c void main(String[] args) {

int[] a = {1, 3, -2, 8, 5};

SegmentTreeRMQ st = new SegmentTreeRMQ(a);

[Link]([Link](1, 3)); // -2

[Link](2, 10);

[Link]([Link](1, 3)); // 3
 }

Complexity: O(log n) per update/query, O(n) space.

Burst Balloons (LeetCode 312)

One-line: Maximize coins by burs ng balloons in op mal order; DP over intervals O(n^3).

// [Link]

public class BurstBalloons {

public sta c int maxCoins(int[] nums) {

int n = [Link];

int[] a = new int[n + 2];

a[0] = 1; a[n + 1] = 1;

for (int i = 0; i < n; i++) a[i + 1] = nums[i];

int[][] dp = new int[n + 2][n + 2];

for (int len = 1; len <= n; len++) {

for (int le = 1; le <= n - len + 1; le ++) {

int right = le + len - 1;

for (int k = le ; k <= right; k++) {

int gain = a[le - 1] * a[k] * a[right + 1];

gain += dp[le ][k - 1] + dp[k + 1][right];

dp[le ][right] = [Link](dp[le ][right], gain);

return dp[1][n];

public sta c void main(String[] args) {

int[] nums = {3,1,5,8};

[Link](maxCoins(nums)); // 167
 }

Complexity: O(n^3) me, O(n^2) space.

Merge Stones (general K)

One-line: Minimum cost to merge stones into one pile when only K consecu ve piles can be merged
at a me; return -1 if impossible.

// [Link]

import java.u l.*;

public class MergeStones {

// stones: array, K: number piles merged at once

public sta c int mergeStones(int[] stones, int K) {

int n = [Link];

if ((n - 1) % (K - 1) != 0) return -1; // impossible condi on

long[] prefix = new long[n + 1];

for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];

int[][] dp = new int[n][n];

for (int len = 2; len <= n; len++) {

for (int i = 0; i + len <= n; i++) {

int j = i + len - 1;

dp[i][j] = Integer.MAX_VALUE;

// split into two parts such that resul ng parts can be merged properly

for (int m = i; m < j; m += K - 1) {

if (dp[i][m] == Integer.MAX_VALUE || dp[m + 1][j] == Integer.MAX_VALUE) con nue;

dp[i][j] = [Link](dp[i][j], dp[i][m] + dp[m + 1][j]);

// if can merge into one pile (i.e., (len-1) % (K-1) == 0), add sum cost

if ((len - 1) % (K - 1) == 0) {

long sum = prefix[j + 1] - prefix[i];

 dp[i][j] = (int)(dp[i][j] == Integer.MAX_VALUE ? Integer.MAX_VALUE : dp[i][j] + sum);

return dp[0][n - 1] >= Integer.MAX_VALUE ? -1 : dp[0][n - 1];

public sta c void main(String[] args) {

int[] stones = {3,2,4,1};

int K = 2;

[Link](mergeStones(stones, K)); // 20 (classic example)

Complexity: O(n^3 / (K-1)) roughly; O(n^2) space. (This DP is the standard op mized split by stepping
m by K-1.)

2. Strings

 Easy

o Longest common prefix

o Check anagram strings

o First unique character

o Valid palindrome string

1. Longest Common Prefix

// LongestCommonPrefi[Link]

// Problem: Find the longest common prefix string among an array of strings.

public class LongestCommonPrefix {

public sta c String longestCommonPrefix(String[] strs) {

if (strs == null || [Link] == 0) return "";

String prefix = strs[0];

 for (int i = 1; i < [Link]; i++) {

while (!strs[i].startsWith(prefix)) {

prefix = prefi[Link](0, prefi[Link]() - 1);

if (prefi[Link]()) return "";

return prefix;

public sta c void main(String[] args) {

String[] arr = {"flower", "flow", "flight"};

[Link](longestCommonPrefix(arr)); // "fl"

Complexity: O(n * m) where n = number of strings, m = min string length.

2. Check Anagram Strings

// [Link]

// Problem: Check if two strings are anagrams (contain same characters in any order).

import java.u l.*;

public class CheckAnagram {

public sta c boolean isAnagram(String s, String t) {

if ([Link]() != [Link]()) return false;

int[] count = new int[26];

for (char c : [Link]()) count[c - 'a']++;

for (char c : [Link]()) {

if (--count[c - 'a'] < 0) return false;

return true;

}
 public sta c void main(String[] args) {

[Link](isAnagram("listen", "silent")); // true

[Link](isAnagram("rat", "car")); // false

Complexity: O(n) me, O(1) space.

3. First Unique Character

// [Link]

// Problem: Find the index of the first non-repea ng character in a string.

public class FirstUniqueCharacter {

public sta c int firstUniqChar(String s) {

int[] count = new int[26];

for (char c : [Link]()) count[c - 'a']++;

for (int i = 0; i < [Link](); i++) {

if (count[[Link](i) - 'a'] == 1) return i;

return -1;

public sta c void main(String[] args) {

[Link](firstUniqChar("leetcode")); // 0

[Link](firstUniqChar("loveleetcode"));// 2

[Link](firstUniqChar("aabb")); // -1

Complexity: O(n) me, O(1) space.

4. Valid Palindrome String

// [Link]
// Problem: Check if a string is a palindrome considering only alphanumeric chars, ignoring cases.

public class ValidPalindrome {

public sta c boolean isPalindrome(String s) {

int l = 0, r = [Link]() - 1;

while (l < r) {

while (l < r && ![Link] erOrDigit([Link](l))) l++;

while (l < r && ![Link] erOrDigit([Link](r))) r--;

if ([Link]([Link](l)) != [Link]([Link](r))) {

return false;

l++;

r--;

return true;

public sta c void main(String[] args) {

[Link](isPalindrome("A man, a plan, a canal: Panama")); // true

[Link](isPalindrome("race a car")); // false

Complexity: O(n) me, O(1) space.

 Medium

o Check rotated palindrome string

o Group anagrams

o Longest substring without repea ng chars

o Minimum window substring

o Longest palindromic substring

o Longest common subsequence

o Edit distance
 o Wildcard matching

o Regular expression matching

o Word search

o Pascal triangle (string representa on some mes)

import java.u l.*;

/**

* [Link]

* Op mized Java implementa ons for common string / dynamic programming problems.

* Each method begins with a one-line problem statement and contains step-by-step

* comments explaining the approach and complexity.

* Usage: open this file in the editor and run the main() for quick examples/tests.

*/

public class StringAlgorithms {

// 1) Check rotated palindrome string: Determine if any rota on of s is a

palindrome.
// Time: O(n^2) worst-case, Space: O(1)

public sta c boolean isRotatedPalindrome(String s) {

if (s == null) return false;

int n = [Link]();

if (n <= 1) return true;

// For each rota on offset, check palindrome using modular indexing (no new strings)

for (int shi = 0; shi < n; shi ++) {

int l = 0, r = n - 1;

boolean ok = true;

while (l < r) {

// compare characters in rotated posi ons using modulus

if ([Link]((shi + l) % n) != [Link]((shi + r) % n)) {

 ok = false;

break; // this rota on is not palindrome

l++;

r--;

if (ok) return true; // found a rota on that is palindrome

return false;

// 2) Group anagrams: Group strings that are anagrams of each other.

// Time: O(k * m) where k = number of strings, m = average length; Space: O(k*m)

public sta c List<List<String>> groupAnagrams(String[] strs) {

Map<String, List<String>> map = new HashMap<>();

for (String s : strs) {

// build a 26-char-frequency key instead of sor ng (faster for longer strings)

int[] freq = new int[26];

for (char c : [Link]()) freq[c - 'a']++;

StringBuilder key = new StringBuilder();

for (int v : freq) {

// delimiter '#' avoids collisions like "11" vs "1"+"1"

[Link](v).append('#');

String k = [Link]();

[Link](k, z -> new ArrayList<>()).add(s);

return new ArrayList<>([Link]());

// 3) Longest substring without repea ng chars: return the substring itself.

 // Time: O(n), Space: O(1) (alphabet size fixed)

public sta c String longestUniqueSubstr(String s) {

if (s == null || [Link]()) return "";

int[] last = new int[128]; // store last seen index for ASCII

Arrays.fill(last, -1);

int start = 0, bestLen = 0, bestStart = 0;

for (int i = 0; i < [Link](); i++) {

char c = [Link](i);

// move start to the right of previous occurrence if needed

start = [Link](start, last[c] + 1);

if (i - start + 1 > bestLen) {

bestLen = i - start + 1;

bestStart = start;

last[c] = i; // update last seen

return [Link](bestStart, bestStart + bestLen);

// 4) Minimum window substring: smallest substring of s containing all

chars of t.
// Time: O(n + m) where n = [Link], m = [Link] (alphabet-sized arrays), Space: O(1)

public sta c String minWindow(String s, String t) {

if (s == null || t == null || [Link]() < [Link]()) return "";

int[] need = new int[128];

for (char c : [Link]()) need[c]++;

int required = 0;

for (int x : need) if (x > 0) required++;

int[] window = new int[128];

int formed = 0, le = 0, right = 0;

 int bestLen = Integer.MAX_VALUE, bestLe = 0;

while (right < [Link]()) {

char c = [Link](right);

window[c]++;

// when a char's frequency matches required frequency, we increment formed

if (need[c] > 0 && window[c] == need[c]) formed++;

// try to contract while the window sa sfies all required dis nct chars

while (le <= right && formed == required) {

if (right - le + 1 < bestLen) {

bestLen = right - le + 1;

bestLe = le ;

char d = [Link](le );

if (need[d] > 0 && window[d] == need[d]) formed--;

window[d]--;

le ++;

right++;

return bestLen == Integer.MAX_VALUE ? "" : [Link](bestLe , bestLe + bestLen);

// 5) Longest palindromic substring: Manacher's algorithm (O(n) me, O(n)

space).
// Time: O(n), Space: O(n)

public sta c String longestPalindrome(String s) {

if (s == null || [Link]() == 0) return "";

// Transform s into t with separators to handle even-length palindromes uniformly.

StringBuilder t = new StringBuilder("^");

 for (int i = 0; i < [Link](); i++) {

[Link]('#').append([Link](i));

[Link]("#$");

char[] arr = [Link]().toCharArray();

int n = [Link];

int[] p = new int[n]; // p[i] = radius of palindrome centered at i

int center = 0, right = 0;

for (int i = 1; i < n - 1; i++) {

int mirror = 2 * center - i;

if (i < right) p[i] = [Link](right - i, p[mirror]);

// expand around center i

while (arr[i + (1 + p[i])] == arr[i - (1 + p[i])]) p[i]++;

// update center and right boundary

if (i + p[i] > right) {

center = i;

right = i + p[i];

// find max length and center

int maxLen = 0, centerIndex = 0;

for (int i = 1; i < n - 1; i++) {

if (p[i] > maxLen) {

maxLen = p[i];

centerIndex = i;

// convert centerIndex back to original string indices

int start = (centerIndex - maxLen) / 2; // integer division

return [Link](start, start + maxLen);

}
// 6) Longest common subsequence: return one LCS string (not just length).
// Time: O(m*n), Space: O(m*n) for DP table (can be op mized to O(min(m,n))).

public sta c String lcs(String a, String b) {

if (a == null || b == null) return "";

int m = [Link](), n = [Link]();

int[][] dp = new int[m + 1][n + 1];

// build dp from bo om-right to top-le

for (int i = m - 1; i >= 0; i--) {

for (int j = n - 1; j >= 0; j--) {

if ([Link](i) == [Link](j)) dp[i][j] = 1 + dp[i + 1][j + 1];

else dp[i][j] = [Link](dp[i + 1][j], dp[i][j + 1]);

// reconstruct one LCS using dp table

StringBuilder sb = new StringBuilder();

int i = 0, j = 0;

while (i < m && j < n) {

if ([Link](i) == [Link](j)) {

[Link]([Link](i));

i++; j++;

} else if (dp[i + 1][j] >= dp[i][j + 1]) i++;

else j++;

return [Link]();

// 7) Edit distance (Levenshtein): minimum edits to convert a -> b.

// Time: O(m*n), Space: O(min(m,n)) using two-row op miza on.

public sta c int editDistance(String a, String b) {

if (a == null) a = "";
 if (b == null) b = "";

int m = [Link](), n = [Link]();

// ensure n <= m to minimize space

if (n > m) return editDistance(b, a); // symmetric, but note opera ons count s ll same

int[] prev = new int[n + 1];

int[] curr = new int[n + 1];

for (int j = 0; j <= n; j++) prev[j] = j; // cost of conver ng empty a to b[0..j]

for (int i = 1; i <= m; i++) {

curr[0] = i; // cost of conver ng a[0..i] to empty b

for (int j = 1; j <= n; j++) {

if ([Link](i - 1) == [Link](j - 1)) curr[j] = prev[j - 1];

else curr[j] = 1 + [Link](prev[j - 1], [Link](prev[j], curr[j - 1]));

// replace = prev[j-1], delete = prev[j], insert = curr[j-1]

int[] tmp = prev; prev = curr; curr = tmp; // swap rows

return prev[n];

// 8) Wildcard matching: pa ern with '?' (single) and '*' (matches any
sequence).
// Time: O(n + m) greedy approach, Space: O(1)

public sta c boolean isWildcardMatch(String s, String p) {

int i = 0, j = 0;

int star = -1, iA erStar = -1;

while (i < [Link]()) {

if (j < [Link]() && ([Link](j) == '?' || [Link](j) == [Link](i))) {

i++; j++; // match single char

} else if (j < [Link]() && [Link](j) == '*') {

 star = j; // remember posi on of '*'

iA erStar = i; // remember where in s we were

j++; // try to match zero chars first

} else if (star != -1) {

// backtrack: let '*' match one more char

j = star + 1;

iA erStar++;

i = iA erStar;

} else {

return false; // no match and no '*' to absorb mismatches

// skip trailing '*' in pa ern

while (j < [Link]() && [Link](j) == '*') j++;

return j == [Link]();

// 9) Regular expression matching: '.' matches any single char, '*' matches
zero or more of preceding element.
// Time: O(m*n) DP, Space: O(m*n)

public sta c boolean isRegexMatch(String s, String p) {

if (s == null || p == null) return false;

int m = [Link](), n = [Link]();

boolean[][] dp = new boolean[m + 1][n + 1];

dp[0][0] = true;

// pa erns like a* or a*b* can match empty string

for (int j = 2; j <= n; j++) {

if ([Link](j - 1) == '*') dp[0][j] = dp[0][j - 2];

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

 char pc = [Link](j - 1);

if (pc == '*') {

// zero occurrences of preceding element

dp[i][j] = dp[i][j - 2] ||

(([Link](j - 2) == '.' || [Link](j - 2) == [Link](i - 1)) && dp[i - 1][j]);

} else if (pc == '.' || pc == [Link](i - 1)) {

dp[i][j] = dp[i - 1][j - 1];

} else {

dp[i][j] = false;

return dp[m][n];

// 10) Word search (board): check if word exists by DFS/backtracking.

// Time: O(m*n*4^L) worst-case where L = word length, Space: O(L) recursion stack

public sta c boolean exist(char[][] board, String word) {

if (board == null || [Link] == 0 || word == null) return false;

int m = [Link], n = board[0].length;

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (board[i][j] == [Link](0) && dfs(board, i, j, word, 0)) return true;

return false;

private sta c boolean dfs(char[][] board, int r, int c, String w, int idx) {

if (idx == [Link]() - 1) return board[r][c] == [Link](idx);

if (board[r][c] != [Link](idx)) return false;

 char tmp = board[r][c];

board[r][c] = '#'; // mark visited

int m = [Link], n = board[0].length;

int[] dr = {-1, 1, 0, 0};

int[] dc = {0, 0, -1, 1};

boolean found = false;

for (int k = 0; k < 4; k++) {

int nr = r + dr[k], nc = c + dc[k];

if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] != '#') {

if (dfs(board, nr, nc, w, idx + 1)) { found = true; break; }

board[r][c] = tmp; // restore

return found;

// 11) Pascal triangle (string representa on): generate rows as space-

separated strings.
// Time: O(numRows^2), Space: O(numRows^2)

public sta c List<String> pascalTriangle(int numRows) {

List<String> result = new ArrayList<>();

if (numRows <= 0) return result;

List<Integer> prev = new ArrayList<>();

for (int r = 0; r < numRows; r++) {

List<Integer> cur = new ArrayList<>(r + 1);

for (int i = 0; i <= r; i++) {

if (i == 0 || i == r) [Link](1);

else [Link]([Link](i - 1) + [Link](i));

// convert to space-separated string representa on

StringBuilder sb = new StringBuilder();

 for (int i = 0; i < [Link](); i++) {

if (i > 0) [Link](' ');

[Link]([Link](i));

[Link]([Link]());

prev = cur;

return result;

// Quick main with small tests for each func on.

public sta c void main(String[] args) {

[Link]("1) isRotatedPalindrome:\n 'aab' -> " + isRotatedPalindrome("aab"));

[Link]("\n2) groupAnagrams:");

String[] arr = {"eat","tea","tan","ate","nat","bat"};

[Link](groupAnagrams(arr));

[Link]("\n3) longestUniqueSubstr:\n 'abcabcbb' -> " +

longestUniqueSubstr("abcabcbb"));

[Link]("\n4) minWindow:\n s='ADOBECODEBANC', t='ABC' -> '" +

minWindow("ADOBECODEBANC","ABC") + "'");

[Link]("\n5) longestPalindrome:\n 'babad' -> " + longestPalindrome("babad"));

[Link]("\n6) lcs:\n 'abcd1e2','bc12ea' -> " + lcs("abcd1e2", "bc12ea"));

[Link]("\n7) editDistance:\n 'ki en','si ng' -> " + editDistance("ki en","si ng"));

[Link]("\n8) isWildcardMatch:\n s='adceb', p='*a*b' -> " +

isWildcardMatch("adceb","*a*b"));
 [Link]("\n9) isRegexMatch:\n s='aab', p='c*a*b' -> " +
isRegexMatch("aab","c*a*b"));

[Link]("\n10) exist (word search):");

char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};

[Link](" word='ABCCED' -> " + exist(board, "ABCCED"));

[Link]("\n11) pascalTriangle (5 rows):");

List<String> p = pascalTriangle(5);

for (String row : p) [Link](" " + row);

 Hard

o Dis nct subsequences count

o Interleaving string problem

o Shortest common supersequence

o Minimum window substring II

1. Dis nct Subsequences Count

Problem Statement:
Given two strings s and t, count the number of dis nct subsequences of s that equal t.
A subsequence of a string is formed by dele ng some (possibly zero) characters without disturbing
the rela ve order of the remaining characters.

Example:
Input: s = "rabbbit", t = "rabbit"
Output: 3

There are 3 dis nct subsequences of "rabbbit" that equal "rabbit".

Java Code:

class Dis nctSubsequences {

public int numDis nct(String s, String t) {

int m = [Link](), n = [Link]();

int[][] dp = new int[m + 1][n + 1];

 // Every string has exactly 1 subsequence equal to "" (empty string)

for (int i = 0; i <= m; i++) {

dp[i][0] = 1;

// Fill DP table

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

if ([Link](i - 1) == [Link](j - 1)) {

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

} else {

dp[i][j] = dp[i - 1][j];

return dp[m][n];

public sta c void main(String[] args) {

Dis nctSubsequences ds = new Dis nctSubsequences();

[Link]([Link] nct("rabbbit", "rabbit")); // Output: 3

Time Complexity: O(m * n)

2. Interleaving String Problem

Problem Statement:
Given three strings s1, s2, and s3, return true if s3 is formed by an interleaving of s1 and s2.
An interleaving means maintaining the rela ve order of characters from s1 and s2.
Example:
Input: s1 = "abc", s2 = "def", s3 = "adbcef"
Output: true

Java Code:

class InterleavingString {

public boolean isInterleave(String s1, String s2, String s3) {

int m = [Link](), n = [Link]();

if (m + n != [Link]()) return false;

boolean[][] dp = new boolean[m + 1][n + 1];

dp[0][0] = true;

for (int i = 0; i <= m; i++) {

for (int j = 0; j <= n; j++) {

if (i > 0 && [Link](i - 1) == [Link](i + j - 1))

dp[i][j] = dp[i][j] || dp[i - 1][j];

if (j > 0 && [Link](j - 1) == [Link](i + j - 1))

dp[i][j] = dp[i][j] || dp[i][j - 1];

return dp[m][n];

public sta c void main(String[] args) {

InterleavingString il = new InterleavingString();

[Link]([Link]("abc", "def", "adbcef")); // true

Time Complexity: O(m * n)

3. Shortest Common Supersequence (SCS)

Problem Statement:
Given two strings s1 and s2, return the shortest string that contains both s1 and s2 as subsequences.
If mul ple answers exist, return any one.

Example:
Input: s1 = "abac", s2 = "cab"
Output: "cabac"

Java Code:

class ShortestCommonSupersequence {

public String shortestCommonSupersequence(String str1, String str2) {

int m = [Link](), n = [Link]();

int[][] dp = new int[m + 1][n + 1];

// Longest Common Subsequence (LCS) DP

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

if ([Link](i - 1) == [Link](j - 1)) {

dp[i][j] = 1 + dp[i - 1][j - 1];

} else {

dp[i][j] = [Link](dp[i - 1][j], dp[i][j - 1]);

// Reconstruct SCS

StringBuilder sb = new StringBuilder();

int i = m, j = n;

while (i > 0 && j > 0) {

if ([Link](i - 1) == [Link](j - 1)) {

[Link]([Link](i - 1));

i--; j--;

} else if (dp[i - 1][j] > dp[i][j - 1]) {

[Link]([Link](i - 1));
 i--;

} else {

[Link]([Link](j - 1));

j--;

while (i > 0) [Link]([Link](--i));

while (j > 0) [Link]([Link](--j));

return [Link]().toString();

public sta c void main(String[] args) {

ShortestCommonSupersequence scs = new ShortestCommonSupersequence();

[Link]([Link]("abac", "cab")); // cabac

Time Complexity: O(m * n)

4. Minimum Window Substring II

Problem Statement:
Given a string s and a list of words words[], find the minimum window substring of s that contains all
the words from words (in any order). If no such substring exists, return an empty string.

Example:
Input: s = "barfoobazbit", words = {"foo", "baz"}
Output: "foobaz"

Java Code:

import java.u l.*;

class MinimumWindowSubstringII {

public String minWindow(String s, String[] words) {

Map<String, Integer> wordCount = new HashMap<>();

 for (String w : words) [Link](w, [Link](w, 0) + 1);

int totalLen = [Link](words).mapToInt(String::length).sum();

int minLen = Integer.MAX_VALUE, start = -1;

for (int i = 0; i <= [Link]() - totalLen; i++) {

String sub = [Link](i, i + totalLen);

if (isValid(sub, wordCount)) {

if ([Link]() < minLen) {

minLen = [Link]();

start = i;

return start == -1 ? "" : [Link](start, start + minLen);

private boolean isValid(String sub, Map<String, Integer> wordCount) {

Map<String, Integer> seen = new HashMap<>();

for (String w : [Link]()) {

int count = 0, idx = 0;

while ((idx = [Link](w, idx)) != -1) {

count++;

idx += [Link]();

if (count < [Link](w)) return false;

[Link](w, count);

return true;

public sta c void main(String[] args) {

 MinimumWindowSubstringII mw = new MinimumWindowSubstringII();

String[] words = {"foo", "baz"};

[Link]([Link]("barfoobazbit", words)); // foobaz

Time Complexity:

 Worst-case O(n * w * k) (where n = string length, w = number of words, k = avg word length).

 Can be op mized using Trie + Sliding Window.

7. Puzzles & Brain Teasers

 Easy

o N players in knockout → number of matches

o 100 doors toggling puzzle

o Find 2nd fastest horse

o Find winner in a round-robin tournament

o Coin toss probability puzzle

o Two players alternately picking stones

o Find champion among N players with 1 loss allowed

o Simple balance puzzle with 3 coins

N players in knockout → number of matches

One-line: In a single-elimina on (knockout) tournament with N players there are N - 1 matches.

// [Link]

import java.u [Link];

public class KnockoutMatches {

public sta c void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("N players: ");

long N = [Link]();

if (N <= 0) { [Link]("N must be > 0"); return; }

 [Link]("Matches played: " + (N - 1));

100 doors toggling puzzle

One-line: A er toggling door i on every i-th pass for 100 doors, only perfect-square-numbered doors
remain open.

// [Link]

public class HundredDoors {

public sta c void main(String[] args) {

int n = 100;

boolean[] open = new boolean[n+1]; // 1..100

for (int pass = 1; pass <= n; pass++) {

for (int door = pass; door <= n; door += pass) open[door] = !open[door];

[Link]("Open doors:");

for (int i = 1; i <= n; i++) if (open[i]) [Link](i + " ");

[Link]();

// op onally show why: count of perfect squares

[Link]("Count open = " + (int)[Link](n));

Find 2nd fastest horse

One-line: Find the second-fastest horse by scanning through the speeds keeping track of the fastest
and second-fastest in one pass (min comparisons).

// [Link]

import java.u [Link];

public class SecondFastest {

public sta c void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("Number of horses: ");

int n = [Link]();
 double[] speed = new double[n];

for (int i = 0; i < n; i++) {

[Link]("Speed of horse " + (i+1) + ": ");

speed[i] = [Link]();

if (n < 2) { [Link]("Need at least 2 horses."); return; }

int best = 0, second = -1;

for (int i = 1; i < n; i++) {

if (speed[i] > speed[best]) { second = best; best = i; }

else if (second == -1 || speed[i] > speed[second]) { second = i; }

[Link] ("Fastest: horse %d (%.3f)\n", best+1, speed[best]);

[Link] ("2nd fastest: horse %d (%.3f)\n", second+1, speed[second]);

Find winner in a round-robin tournament

One-line: In a round-robin where every pair plays once, the winner is the player with the most wins
( e-break rules may be needed).

// [Link]

import java.u [Link];

public class RoundRobinWinner {

// Input: n, then n lines of n entries: for i!=j put 1 if i beat j else 0; diagonal ignored or 0

public sta c void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("Number of players: ");

int n = [Link]();

int[][] res = new int[n][n];

[Link]("Enter results matrix (1 if row beat column, else 0):");

for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) res[i][j] = [Link]();

int best = -1, bestWins = -1;

for (int i = 0; i < n; i++) {

 int wins = 0;

for (int j = 0; j < n; j++) if (res[i][j] == 1) wins++;

if (wins > bestWins) { bestWins = wins; best = i; }

[Link]("Winner (most wins): Player " + (best + 1) + " with " + bestWins + " wins.");

Coin toss probability puzzle

One-line: The probability of ge ng exactly k heads in n fair coin tosses is C(n,k) * (1/2)^n.

// [Link]

import java.u [Link];

import [Link];

public class CoinProbability {

sta c BigInteger comb(int n, int k) {

if (k < 0 || k > n) return [Link];

k = [Link](k, n - k);

BigInteger num = [Link], den = [Link];

for (int i = 1; i <= k; i++) {

num = [Link] ply([Link](n - k + i));

den = [Link] ply([Link](i));

return [Link](den);

public sta c void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("n tosses: ");

int n = [Link]();

[Link]("k heads: ");

int k = [Link]();

BigInteger c = comb(n, k);

double prob = [Link]() * [Link](0.5, n);

 [Link] ("P(exactly %d heads in %d tosses) = %.10f (comb = %s)\n", k, n, prob,
[Link]());

Two players alternately picking stones

One-line: Given N stones and each player may remove 1..M stones per turn, determine whether the
first player has a forced win (normal play).

// [Link]

import java.u [Link];

public class TakeStones {

public sta c void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("Total stones N: ");

int N = [Link]();

[Link]("Max remove M: ");

int M = [Link]();

boolean[] win = new boolean[N+1];

win[0] = false;

for (int s = 1; s <= N; s++) {

win[s] = false;

for (int r = 1; r <= M && r <= s; r++) if (!win[s-r]) { win[s] = true; break; }

[Link]("First player " + (win[N] ? "wins" : "loses") + " with op mal play.");

if (win[N]) {

for (int r = 1; r <= M && r <= N; r++) if (!win[N-r]) { [Link]("Winning first move:
remove " + r); break; }

Find champion among N players with 1 loss allowed (double-elimina on)

One-line: In a double-elimina on (each player eliminated a er 2 losses) tournament, simulate
matches un l only one player remains with fewer than 2 losses — that player is champion.
// DoubleElimina [Link]

import java.u l.*;

public class DoubleElimina onSim {

// Simple skill-based determinis c match: higher skill wins

sta c class Player { int id; double skill; int losses; Player(int i, double s){id=i;skill=s;losses=0;} }

public sta c void main(String[] args){

Scanner sc=new Scanner([Link]);

[Link]("Number of players N: "); int N=[Link]();

List<Player> players=new ArrayList<>();

Random rnd=new Random(1);

for(int i=0;i<N;i++){

[Link]("Skill of player "+(i+1)+": ");

double s = [Link]();

[Link](new Player(i+1,s));

List<Player> ac ve=new ArrayList<>(players);

while(true){

// remove players with 2 or more losses

ac [Link](p -> [Link] >= 2);

if (ac [Link]() <= 1) break;

Collec [Link]ffle(ac ve, rnd);

// pair adjacent, if odd last gets bye

List<Player> nextRound = new ArrayList<>();

for (int i = 0; i < ac [Link](); i += 2) {

if (i+1 >= ac [Link]()) { [Link](ac [Link](i)); break; }

Player a = ac [Link](i), b = ac [Link](i+1);

Player winner = [Link] >= [Link] ? a : b;

Player loser = winner==a?b:a;

[Link]++;

[Link](winner);
 [Link]("Match: P"+[Link]+" vs P"+[Link]+" -> winner: P"+[Link]+" (losses now
P"+[Link]+":"+[Link]+")");

ac ve = new ArrayList<>(nextRound);

// champion is remaining player (or e if none)

ac [Link](p -> [Link] >= 2);

if (ac [Link]()==1) [Link]("Champion: Player " + ac [Link](0).id);

else [Link]("No champion found (all eliminated).");

Simple balance puzzle with 3 coins

One-line: With 3 coins and one counterfeit (unknown heavier or lighter), one weighing on a balance
scale can iden fy which coin is counterfeit and whether it is heavier or lighter.

// [Link]

import java.u [Link];

public class ThreeCoinBalance {

// We represent coins as weights: genuine=10, fake heavier=11, fake lighter=9

public sta c void main(String[] args){

Scanner sc=new Scanner([Link]);

[Link]("Enter fake coin index (1..3) and type (H for heavier, L for lighter).");

[Link]("Fake index: ");

int idx = [Link]();

[Link]("Type H or L: ");

char t = [Link]().toUpperCase().charAt(0);

int[] w = new int[4];

for (int i = 1; i <= 3; i++) w[i] = 10;

w[idx] = (t=='H') ? 11 : 9;

// Weigh coin1 vs coin2

[Link]("Weighing: coin1 vs coin2");

if (w[1] == w[2]) {
 [Link]("Scale balances -> counterfeit is coin3 and it is " + (w[3] > 10 ? "heavier" :
"lighter"));

} else if (w[1] > w[2]) {

[Link]("Le heavier -> counterfeit is coin1 (heavier) or coin2 (lighter).");

// with 3 coins logic: since coin3 wasn't on scale, deduce:

if (w[1] > w[2]) [Link]("Therefore counterfeit is coin1 and it is heavier, or coin2

and it is lighter.");

// but we already know actual from inputs; print resolved:

[Link]("Actual: coin " + idx + " is counterfeit and " + (t=='H' ? "heavier" :
"lighter"));

} else {

[Link]("Right heavier -> counterfeit is coin2 (heavier) or coin1 (lighter).");

[Link]("Actual: coin " + idx + " is counterfeit and " + (t=='H' ? "heavier" :
"lighter"));

 Medium

o 25 horses → find top 3

o 9 balls heavier puzzle

o 12 balls defec ve puzzle

o Egg drop puzzle (2 eggs, 100 floors)

o Poisoned wine bo les puzzle

o Josephus problem

o Prisoner puzzle with light bulb

o Prisoner hat puzzle

o Tournament with losers’ bracket

o Find top 5 horses from 100

o Weighing puzzle with 27 coins

o Domino ling on chessboard puzzle

 o Card shuffle restore opera ons

o Knights on chessboard puzzle

o Two water jug problem

o Gas sta on problem

o Candy distribu on problem

Puzzle 1: 25 Horses → Find Top 3

Problem:
You have 25 horses, 5 tracks, no stopwatch. Find the fastest 3 horses with minimum races.

Use Case:
Organizing sprint trials when only 5 lanes are available.

Logic:

 Divide into 5 groups → run 5 races.

 Race group winners → 1 race.

 Only possible top 3 candidates are A1, A2, A3, B1, B2, C1 (from group ranking rules).

 Run 1 more race among them → total 7 races.

import java.u l.*;

class Horses25 {

public sta c void main(String[] args) {

// Assign random "speed" to each horse

double[] horses = new double[25];

Random rand = new Random();

for (int i = 0; i < 25; i++) {

horses[i] = [Link](); // higher = faster

// Step 1: Divide into 5 groups of 5

List<List<Integer>> groups = new ArrayList<>();

for (int g = 0; g < 5; g++) {

 List<Integer> group = new ArrayList<>();

for (int j = 0; j < 5; j++) [Link](g*5 + j);

[Link](group);

// Step 2: Race each group → sort by speed

for (List<Integer> group : groups) {

[Link]((a,b) -> [Link](horses[b], horses[a]));

// Step 3: Winners race

List<Integer> winners = new ArrayList<>();

for (List<Integer> g : groups) [Link]([Link](0));

[Link]((a,b) -> [Link](horses[b], horses[a]));

// Step 4: Select candidates

int A = [Link](0)/5, B = [Link](1)/5, C = [Link](2)/5;

List<Integer> candidates = [Link](

[Link](A).get(1), [Link](A).get(2), // A2, A3

[Link](B).get(0), [Link](B).get(1), // B1, B2

[Link](C).get(0) // C1

);

[Link]((a,b) -> [Link](horses[b], horses[a]));

// Final top 3

[Link]("Top 3 Horses:");

[Link]("1st → Horse " + [Link](0));

[Link]("2nd → Horse " + [Link](0));

[Link]("3rd → Horse " + [Link](1));

}
Output (sample):

Top 3 Horses:

1st → Horse 12

2nd → Horse 7

3rd → Horse 19

Puzzle 2: 9 Balls, One Heavier

Problem:
Find the heavier ball among 9 with only 2 weighings.

Use Case:
Detec ng a defec ve heavy product in a batch using limited tests.

Logic:

 Divide into 3 groups of 3. Weigh group1 vs group2.

 If unequal → heavy is in heavier group.

 Else → heavy is in group3.

 Weigh 2 balls of suspected group.

class NineBalls {

public sta c void main(String[] args) {

int[] balls = new int[9];

int heavy = 5; // hidden heavier ball

for (int i = 0; i < 9; i++) balls[i] = 1;

balls[heavy] = 2;

// Step 1: Weigh 0,1,2 vs 3,4,5

int le = balls[0] + balls[1] + balls[2];

int right = balls[3] + balls[4] + balls[5];

int suspectGroup;

if (le > right) suspectGroup = 0; // 0–2

else if (right > le ) suspectGroup = 3; // 3–5

else suspectGroup = 6; // 6–8

 // Step 2: Weigh first 2 balls of suspect group

int a = suspectGroup, b = suspectGroup+1, c = suspectGroup+2;

if (balls[a] > balls[b]) [Link]("Heavier Ball = " + a);

else if (balls[b] > balls[a]) [Link]("Heavier Ball = " + b);

else [Link]("Heavier Ball = " + c);

Output:

Heavier Ball = 5

Puzzle 3: Egg Drop (2 eggs, 100 floors)

Problem:
Find the minimum worst-case drops needed.

Use Case:
Tes ng fragile goods like glass bulbs.

Logic:

 With 2 eggs, strategy = use first egg in increasing steps.

 Use k + (k-1) + … + 1 ≥ 100 → k = 14.

class EggDrop {

public sta c void main(String[] args) {

int floors = 100;

int moves = 0, covered = 0;

while (covered < floors) {

moves++;

covered += moves;

[Link]("Minimum drops needed = " + moves);

Output:
Minimum drops needed = 14

Puzzle 4: Poisoned Wine Bo les

Problem:
Find poisoned bo le among N bo les using minimum tasters.

Use Case:
Binary coding strategy for lab tes ng.

Logic:

 Number tasters = ceil(log2(N)).

 Each tester drinks from bo les where corresponding bit = 1.

 Death pa ern (binary) = poisoned bo le ID.

class PoisonedWine {

public sta c void main(String[] args) {

int bo les = 1000;

int testers = (int)[Link]([Link](bo les) / [Link](2));

[Link]("Minimum tasters required = " + testers);

int poisoned = 726; // hidden

[Link]("Poisoned bo le = " + poisoned);

[Link]("Binary = " + [Link](poisoned));

Output:

Minimum tasters required = 10

Poisoned bo le = 726

Binary = 1011010110

Puzzle 5: Josephus Problem

Problem:
N people in a circle, every k-th is eliminated un l one remains. Find survivor.

Use Case:
Scheduling or resource elimina on models.
Logic:

 Recursive formula: J(n,k) = (J(n-1,k) + k) % n.

class Josephus {

sta c int josephus(int n, int k) {

if (n == 1) return 0;

return (josephus(n-1, k) + k) % n;

public sta c void main(String[] args) {

int n = 7, k = 3;

int survivor = josephus(n, k) + 1; // +1 for 1-indexed

[Link]("Survivor Posi on = " + survivor);

Output:

Survivor Posi on = 4

Puzzle 6: Prisoners with Light Bulb

Problem:
N prisoners, one light bulb in central room. Prisoners enter randomly. Design a strategy so one
prisoner can eventually announce: “All have visited.”

Use Case:
Distributed systems where mul ple agents must confirm par cipa on.

Logic (Counter Strategy):

 One prisoner = counter.

 Others turn off the bulb only once (if they find it ON).

 Each me the counter finds bulb OFF, he increments his count.

 When counter = N-1, he declares all have visited.

import java.u l.*;

class PrisonersLightBulb {

sta c void simulate(int N) {

 boolean bulb = false;

boolean[] turnedOff = new boolean[N];

int counter = 0, countVisits = 0;

Random rand = new Random();

while (counter < N - 1) {

int p = [Link](N); // random prisoner enters

if (p == 0) { // counter prisoner

if (!bulb) { // bulb is OFF → someone turned it off

counter++;

bulb = true; // turn ON again

} else {

if (!turnedOff[p] && bulb) {

bulb = false;

turnedOff[p] = true;

countVisits++;

[Link]("Counter announces a er " + countVisits + " visits!");

public sta c void main(String[] args) {

simulate(10);

Output (sample):

Counter announces a er 158 visits!

Puzzle 7: Prisoner Hat Puzzle

Problem:
N prisoners wear red/blue hats in a line. Each can only see hats in front. They must guess their own
hat color. Strategy to maximize survival.

Use Case:
Error detec on with parity.

Logic:

 First prisoner announces parity (even/odd number of red hats he sees).

 Each next prisoner can deduce his hat color using previous answers.

 At most 1 prisoner may be wrong, rest guaranteed correct.

class PrisonerHat {

public sta c void main(String[] args) {

int[] hats = {1, 0, 1, 1, 0}; // 1=Red, 0=Blue

int n = [Link];

int redCountAhead = 0;

for (int i = 1; i < n; i++) redCountAhead += hats[i];

// First prisoner announces parity

int guess0 = redCountAhead % 2;

[Link]("Prisoner 0 guesses: " + (guess0==1?"Red":"Blue"));

// Remaining prisoners deduce

int paritySoFar = redCountAhead % 2;

for (int i = 1; i < n; i++) {

int visibleReds = 0;

for (int j = i+1; j < n; j++) visibleReds += hats[j];

int expected = (paritySoFar - visibleReds + 2) % 2;

[Link]("Prisoner " + i + " guesses: " + (expected==1?"Red":"Blue"));

Output:

Prisoner 0 guesses: Blue

Prisoner 1 guesses: Red

Prisoner 2 guesses: Red

Prisoner 3 guesses: Blue

Prisoner 4 guesses: Blue

Puzzle 8: Tournament with Losers’ Bracket

Problem:
Find winner in a double-elimina on tournament (players must lose twice to be out).

Use Case:
eSports or sports compe ons.

Logic:

 Track wins/losses.

 Winner bracket → losers bracket a er 1st loss.

 Final is between winner of winners’ bracket and winner of losers’ bracket.

class DoubleElimina on {

sta c void runTournament(int players) {

int[] losses = new int[players];

Random rand = new Random();

List<Integer> ac ve = new ArrayList<>();

for (int i=0;i<players;i++) ac [Link](i);

while (ac [Link]() > 1) {

int a = ac [Link]([Link](ac [Link]()));

int b = ac [Link]([Link](ac [Link]()));

int winner = [Link]()?a:b;

int loser = (winner==a)?b:a;

losses[loser]++;

if (losses[loser]<2) ac [Link](loser); // move to losers’ bracket

ac [Link](winner);

[Link]("Tournament Winner = Player " + ac [Link](0));

 }

public sta c void main(String[] args) {

runTournament(8);

Output (sample):

Tournament Winner = Player 3

Puzzle 9: Two Water Jug Problem

Problem:
Given two jugs (capacity m,n), measure target d.

Use Case:
Classic “Die Hard 3” puzzle.

Logic:
Use BFS on states (x,y) where x=water in jug1, y=water in jug2. Opera ons: fill, empty, pour.

import java.u l.*;

class WaterJug {

sta c void solve(int m, int n, int d) {

Queue<int[]> q = new LinkedList<>();

Set<String> visited = new HashSet<>();

[Link](new int[]{0,0});

while(![Link]()) {

int[] state = [Link]();

int x=state[0], y=state[1];

if (x==d || y==d) {

[Link]("Solu on found: ("+x+","+y+")");

return;

String key=x+","+y;

if([Link](key)) con nue;

 [Link](key);

// Opera ons

[Link](new int[]{m,y}); // fill jug1

[Link](new int[]{x,n}); // fill jug2

[Link](new int[]{0,y}); // empty jug1

[Link](new int[]{x,0}); // empty jug2

// pour jug1 -> jug2

int pour = [Link](x,n-y);

[Link](new int[]{x-pour,y+pour});

// pour jug2 -> jug1

pour = [Link](y,m-x);

[Link](new int[]{x+pour,y-pour});

[Link]("No solu on!");

public sta c void main(String[] args) {

solve(3,5,4); // classic puzzle

Output:

Solu on found: (3,4)

Puzzle 10: Gas Sta on Problem

Problem:
Given circular gas sta ons with fuel[i] and cost[i], find start index to complete circle.

Use Case:
Op mizing fuel stops in logis cs.
Logic:

 If total gas < total cost → impossible.

 Otherwise, greedy scan to find start.

class GasSta on {

sta c int canTravel(int[] gas, int[] cost) {

int total=0, curr=0, start=0;

for (int i=0;i<[Link];i++) {

total += gas[i]-cost[i];

curr += gas[i]-cost[i];

if (curr<0) {

start = i+1;

curr=0;

return total>=0?start:-1;

public sta c void main(String[] args) {

int[] gas={1,2,3,4,5};

int[] cost={3,4,5,1,2};

[Link]("Start Index = " + canTravel(gas,cost));

Output:

Start Index = 3

Puzzle 11: Candy Distribu on

Problem:
N children in line with ra ngs. Give candies so:

1. Each child gets ≥1.

 2. Higher ra ng than neighbor → more candies.
Minimize total candies.

Use Case:
Fair reward distribu on.

Logic:

 Le -to-right pass → ensure ra ng[i]>ra ng[i-1].

 Right-to-le pass → ensure ra ng[i]>ra ng[i+1].

 Take max of both.

class Candy {

sta c int minCandies(int[] ra ngs) {

int n = ra [Link];

int[] le = new int[n], right = new int[n];

Arrays.fill(le ,1);

Arrays.fill(right,1);

for(int i=1;i<n;i++)

if(ra ngs[i]>ra ngs[i-1]) le [i]=le [i-1]+1;

for(int i=n-2;i>=0;i--)

if(ra ngs[i]>ra ngs[i+1]) right[i]=right[i+1]+1;

int sum=0;

for(int i=0;i<n;i++) sum+=[Link](le [i],right[i]);

return sum;

public sta c void main(String[] args) {

int[] ra ngs={1,0,2};

[Link]("Minimum candies = " + minCandies(ra ngs));

Output:

Minimum candies = 5
 Puzzle 12: 12 Balls Defec ve Puzzle
Problem:
12 iden cal-looking balls, one is odd (heavier or lighter). Find it in 3 weighings.

Use Case:
Iden fying one defec ve product without knowing if it is heavier or lighter.

Logic:

 Split into 3 groups of 4.

 Compare group1 vs group2.

 Depending on result, narrow to 4 candidates.

 Use systema c comparison in 2 more weighings.

class TwelveBalls {

public sta c void main(String[] args) {

// Let’s simulate: ball 7 is defec ve and lighter

int[] balls = new int[12];

for (int i=0;i<12;i++) balls[i]=1;

int defec ve=7; balls[defec ve]=0; // lighter

// First weighing: 0-3 vs 4-7

int le =sum(balls,0,3), right=sum(balls,4,7);

[Link]("Weighing 1: " + le + " vs " + right);

// From logic, narrow down to suspicious group

// Due to complexity, we usually pre-design decision tree

// For demonstra on we just show weighing results

[Link]("Defec ve ball is at index " + defec ve +

" and it is " + (balls[defec ve]>1?"heavier":"lighter"));

sta c int sum(int[] arr,int l,int r){

int s=0; for(int i=l;i<=r;i++) s+=arr[i]; return s;

}
}

Output (example):

Weighing 1: 4 vs 3

Defec ve ball is at index 7 and it is lighter

Puzzle 13: Weighing Puzzle with 27 Coins

Problem:
27 coins, one is heavier. Find it using a balance scale.

Use Case:
Batch tes ng when defec ve item is heavier.

Logic:

 Each weighing divides into 3 groups.

 27 → 9 → 3 → 1 → total 3 weighings.

class Coins27 {

public sta c void main(String[] args) {

int[] coins = new int[27];

for (int i=0;i<27;i++) coins[i]=1;

int heavy=19; coins[heavy]=2;

// Weigh 9 vs 9

int le =sum(coins,0,8), right=sum(coins,9,17);

int start;

if(le >right) start=0;

else if(right>le ) start=9;

else start=18;

// Narrow to 9 coins

le =sum(coins,start,start+2);

right=sum(coins,start+3,start+5);

if(le >right) start=start;

else if(right>le ) start=start+3;

 else start=start+6;

// Narrow to 3 coins

if(coins[start]>coins[start+1])

[Link]("Heavier coin = " + start);

else if(coins[start+1]>coins[start])

[Link]("Heavier coin = " + (start+1));

else

[Link]("Heavier coin = " + (start+2));

sta c int sum(int[] a,int l,int r){int s=0;for(int i=l;i<=r;i++)s+=a[i];return s;}

Output:

Heavier coin = 19

Puzzle 14: Domino Tiling on Chessboard

Problem:
Can a chessboard with two opposite corners removed be led with dominoes (2×1)?

Use Case:
Geometric covering problems.

Logic:

 Chessboard has 32 white + 32 black squares.

 Removing opposite corners removes 2 squares of same color.

 Now imbalance: 30 of one, 32 of other.

 Domino always covers 1 black + 1 white → impossible.

class DominoTiling {

public sta c void main(String[] args) {

[Link]("Can 8x8 board with opposite corners removed be led?");

[Link]("Answer: NO (unequal black/white squares)");

}
Output:

Can 8x8 board with opposite corners removed be led?

Answer: NO (unequal black/white squares)

Puzzle 15: Card Shuffle Restore

Problem:
Given N cards, shuffled by perfect out-shuffle (split in half and interleave). How many shuffles un l
original order?

Use Case:
Card games & cryptographic shuffling.

Logic:

 Out-shuffle is a permuta on.

 Find order of this permuta on (LCM of cycle lengths).

import java.u l.*;

class CardShuffle {

sta c int shuffleOrder(int n) {

int[] perm = new int[n];

int half = n/2;

for(int i=0;i<half;i++){

perm[2*i]=i;

perm[2*i+1]=half+i;

boolean[] seen=new boolean[n];

int lcm=1;

for(int i=0;i<n;i++){

if(!seen[i]){

int len=0, j=i;

while(!seen[j]){

seen[j]=true;

j=perm[j];
 len++;

lcm=lcm(lcm,len);

return lcm;

sta c int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

sta c int lcm(int a,int b){return a/gcd(a,b)*b;}

public sta c void main(String[] args) {

[Link]("Deck size 52 → Restore a er "

+ shuffleOrder(52) + " shuffles");

Output:

Deck size 52 → Restore a er 8 shuffles

Puzzle 16: Knights on Chessboard

Problem:
Place maximum knights on N×N chessboard so none a ack each other.

Use Case:
Resource placement without conflicts.

Logic:

 For N>2, max knights = ceil(N*N / 2).

 Because knights only a ack opposite color squares.

class Knights {

sta c int maxKnights(int n) {

if(n==1) return 1;

if(n==2) return 4;
 return (n*n+1)/2;

public sta c void main(String[] args) {

[Link]("Max knights on 8x8 = " + maxKnights(8));

Output:

Max knights on 8x8 = 32

Puzzle 17: Find Top 5 Horses from 100

Problem:
100 horses, 5 tracks, no stopwatch. Find top 5 fastest with minimum races.

Use Case:
Large tournament selec on.

Logic:

 Race 20 groups → 20 races.

 Race winners → 1 race.

 Then carefully filter candidates (similar to 25-horse logic).

 Total ≈ 24 races (op mal solu on needs deeper reasoning).

class Horses100 {

public sta c void main(String[] args) {

[Link]("100 horses, 5 tracks → need about 24 races to find top 5");

[Link]("Strategy: group races + winners race + filtered finals");

Output:

100 horses, 5 tracks → need about 24 races to find top 5

Strategy: group races + winners race + filtered finals

  Hard

o Generalize find top k horses among n with m tracks

o Prisoner hat puzzle (extended)

o Prisoner light bulb advanced version

o Tournament with loser bracket analysis

o Egg drop with k eggs & n floors

o Bridge crossing puzzle

o Domino ling extensions

o Mul -jug water puzzle

o Wolf-goat-cabbage puzzle

o Advanced Josephus problem variant

Top-k horses among n with m tracks (generalized)

Problem. You have n horses. You can run up to m horses simultaneously on m tracks. A race returns
the horses in rela ve order only (no mes). Find the top k horses while minimizing the number of
races.

Idea / analysis.

 If you have numeric mes (i.e., you can measure speeds), this is a simple selec on problem:
find the k smallest mes — do it in O(n log k) with a max-heap or O(n) expected with
QuickSelect.

 If you only get rela ve order per race (classic puzzle): first you must run ceil(n/m) ini al
races to see each horse once. Use the group rankings to eliminate obviously impossible
candidates and then schedule extra races among the remaining candidates. The exact
minimal number depends on m and k; the classic 25 horses / 5 tracks / top 3 puzzle yields a
clever elimina on reasoning. For general m,k there is no trivial closed form — a tournament-
like elimina on of group winners followed by carefully constructed " e-breaking" races is the
usual approach.

Below are two Java solu ons:

 A prac cal computa onal solu on when numeric mes are available (fast & op mal).

 A simulator version showing the constrained-racing approach (you can adapt it to

experiment with strategies).

A. If mes are known — op mized selec on (O(n log k))

// File: [Link]

import java.u l.*;

public class TopKHorsesByTimes {

// Return indices of top-k fastest horses (0-based), mes[i] = lower is faster

public sta c List<Integer> topK(int[] mes, int k) {

// max-heap of pairs ( me, index)

PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> b[0]-a[0]);

for (int i = 0; i < [Link]; i++) {

if ([Link]() < k) pq.offer(new int[]{ mes[i], i});

else if ( mes[i] < [Link]()[0]) {

[Link]();

pq.offer(new int[]{ mes[i], i});

List<Integer> res = new ArrayList<>();

while (![Link]()) [Link]([Link]()[1]);

Collec [Link](res); // from fastest to slowest among top-k

return res;

public sta c void main(String[] args) {

int[] mes = {50, 45, 60, 42, 55, 41, 49};

int k = 3;

List<Integer> topk = topK( mes, k);

[Link]("Top " + k + " horse indices (fastest first): " + topk);

// sample output: indices poin ng to horses with mes 41,42,45

Complexity: O(n log k) me, O(k) extra space.

B. Simulator (racing constraint: only rela ve order per race)

This is a small framework that simulates races and lets you test heuris cs (not a closed-form op mal
solver).
// File: [Link]

import java.u l.*;

/*

* Simulator: horses have hidden numeric speeds; a "race" takes up to m horses and returns order.

* Heuris c: ini al group races -> race group winners -> run e-breaker races among candidates.

*/

public class HorseRacingSimulator {

int[] speed; // smaller is faster

int m;

int races = 0;

public HorseRacingSimulator(int[] speed, int m) {

[Link] = speed; this.m = m;

// race horses by indices; returns indices sorted by speed ascending (fastest first)

public List<Integer> race(List<Integer> indices) {

races++;

[Link]([Link](i -> speed[i]));

return new ArrayList<>(indices);

// simple heuris c to get top-k: race in groups, then refine among top candidates

public List<Integer> findTopK(int k) {

int n = [Link];

List<List<Integer>> groups = new ArrayList<>();

for (int i = 0; i < n; i += m) {

List<Integer> g = new ArrayList<>();

for (int j = i; j < [Link](n, i + m); j++) [Link](j);

[Link](race(g)); // sorted

}
 // take top 1 from each group -> winners

List<Integer> winners = new ArrayList<>();

for (List<Integer> g : groups) [Link]([Link](0));

// race winners (in groups of size m)

List<Integer> orderedWinners = new ArrayList<>();

for (int i=0;i<[Link]();i+=m) [Link](race([Link](i,

[Link]([Link](), i+m))));

// Candidate set: top-k from each original group corresponding to top groups (heuris c)

Set<Integer> candidates = new HashSet<>();

for (int i=0; i<[Link]([Link](), k); i++){

int winnerIdx = [Link](i);

int groupId = winnerIdx / m;

// take top k (or top m) from that group

for (int j=0; j<[Link](groupId).size() && [Link]() < k*m; j++)

[Link]([Link](groupId).get(j));

// Final: keep racing candidate subsets un l we can pick top-k by sor ng (we can actually use
speeds here)

List<Integer> candList = new ArrayList<>(candidates);

[Link]([Link](i -> speed[i]));

return [Link](0, [Link](k, [Link]()));

public sta c void main(String[] args){

int[] speeds = {100,95,102,90,110,89,101,120,85,99,94,88};

HorseRacingSimulator sim = new HorseRacingSimulator(speeds, 4); // 4-track

List<Integer> top3 = sim.findTopK(3);

[Link]("Top3 indices: " + top3 + ", races used: " + [Link]);

}
Notes: The simulator helps experiment with heuris cs. For provably minimal number of races under
only-order results you must follow a carefully constructed elimina on proof depending on m and k;
the code above demonstrates a usable heuris c.

Prisoners’ hat puzzle (extended: mul ple colors)

Problem. n prisoners in a line (or circle). Each is given a hat color chosen from C colors. Each prisoner
can see some hats (commonly: those in front). They must, in a fixed order, guess their own hat color;
they can hear previous guesses. Devise a strategy maximizing number of correct guesses. Extended
means C>2 (mul -color) and general visibility.

Strategy (mul -color): Use modular arithme c. Beforehand prisoners agree that the first speaker will
encode the sum (mod C) of observed colors. Each subsequent prisoner subtracts observed colors and
previous guesses to deduce their own color. This guarantees that all except possibly the first guess
correctly (so n-1 correct guaranteed).

Java simula on (general C colors)

// File: Mul [Link]

import java.u l.*;

public class Mul ColorHatPuzzle {

// hats: array of ints 0..C-1; prisoner i sees hats[i+1..n-1] if lined up facing forward.

// first prisoner will announce (sum of seen) mod C to encode.

public sta c int simulate(int[] hats, int C) {

int n = [Link];

int[] guesses = new int[n];

int encoded = 0;

for (int j = 1; j < n; j++) encoded = (encoded + hats[j]) % C;

guesses[0] = encoded; // first says encoded value (sacrifice possibly)

for (int i = 1; i < n; i++) {

int sumSeen = 0;

for (int j = i+1; j < n; j++) sumSeen = (sumSeen + hats[j]) % C;

int sumPreviousGuesses = 0;

for (int j = 0; j < i; j++) sumPreviousGuesses = (sumPreviousGuesses + guesses[j]) % C;

// own = encoded - sumSeen - sumPreviousGuesses (mod C)

int own = ((encoded - sumSeen - sumPreviousGuesses) % C + C) % C;

guesses[i] = own;
 }

int correct = 0;

for (int i = 0; i < n; i++) if (guesses[i] == hats[i]) correct++;

[Link]("Hats: " + [Link](hats));

[Link]("Guesses: " + [Link](guesses));

return correct;

public sta c void main(String[] args) {

int[] hats = {2, 0, 1, 2, 1}; // values in 0..C-1

int C = 3;

int correct = simulate(hats, C);

[Link]("Correct guesses: " + correct + " out of " + [Link]);

Guarantee: n-1 correct (first may be wrong). Complexity O(n^2) naive in code; can be O(n) with
running sums.

Prisoners & the light bulb (advanced)

Problem. n prisoners will be randomly brought into a room with a single light bulb (on/off). They may
toggle it. At any me a prisoner can announce “everyone has visited the room at least once” — if
true they all go free. Devise a strategy to guarantee eventual correct announcement. Advanced:
unknown ini al bulb state, many prisoners, or limited number of bulbs.

Standard strategy (one bulb): Designate one prisoner as the counter. All other prisoners will turn the
bulb on exactly once (the first me they find it off and they haven't turned it on before). The counter
turns the bulb off when he finds it on, increasing his count by 1. When the counter’s count reaches n-
1 he knows everyone has visited at least once (assuming ini al bulb off). If ini al state unknown, you
can have the counter treat the first on as uncounted (or run a preface to normalize). Advanced
versions vary details (use mul ple bulbs to parallelize, or use ternary encoding, etc.)

Java simula on (random visits, unknown ini al state handled)

// File: [Link]

import java.u l.*;

public class LightBulbPrisoners {

sta c class Simulator {

boolean bulb; // true == ON

int n;

boolean[] hasTurnedOn;

int counterCount = 0;

int counterId;

Random rnd = new Random();

public Simulator(int n, boolean ini alState) {

this.n = n;

bulb = ini alState;

hasTurnedOn = new boolean[n];

counterId = 0; // choose prisoner 0 as counter

// simulate random visit ordering un l counter declares

public int run() {

int steps = 0;

// to handle unknown ini al state: ignore first me counter sees ON (treat as not coun ng)

boolean counterFirstOnIgnored = false;

while (true) {

int p = [Link](n);

steps++;

if (p == counterId) {

if (bulb) {

if (!counterFirstOnIgnored) {

// ignore the first observed ON to deal with unknown ini al bulb

counterFirstOnIgnored = true;

bulb = false; // counter turns it off but doesn't count

} else {

bulb = false;
 counterCount++;

if (counterCount >= n - 1) return steps;

} else {

// normal prisoner: if they haven't contributed before and bulb is OFF => turn ON once

if (!hasTurnedOn[p] && !bulb) {

bulb = true;

hasTurnedOn[p] = true;

public sta c void main(String[] args) {

Simulator sim = new Simulator(10, true); // ini al bulb state true (ON)

int steps = [Link]();

[Link]("Steps un l declara on: " + steps);

Notes: The expected number of visits can be large. Complexity is simula on-dependent; strategy
guarantees eventual success.

Tournament with loser bracket analysis (double elimina on)

Problem. Analyze a tournament with a loser (double-elimina on) bracket. How many matches are
needed, how to schedule, what about finding top k?

Key facts.

 Single-elimina on needs n-1 matches.

 Double-elimina on (each player must lose twice to be eliminated) has at most 2n - 1

matches in the worst case. Reason: each match creates one loss; to eliminate n-1 players you
need 2*(n-1) losses, plus the champion might lose once in the final (so up to 2n-1).
  If you need a ranked top k, extra matches are required — scheduling depends on whether
you allow consola on brackets.

Java u lity: compute match counts and simulate bracket sizes

// File: [Link]

public class TournamentAnalysis {

// Maximum matches for double-elimina on

public sta c int maxMatchesDoubleElim(int n) {

if (n <= 0) return 0;

return 2 * n - 1;

public sta c void main(String[] args) {

[Link]("Single-elim matches for n=16: " + (16 - 1));

[Link]("Double-elim max matches for n=16: " + maxMatchesDoubleElim(16));

Scheduling note: To get precise match schedule for top-k you usually:

 Run full single/double-elim to locate champion and finalists.

 Op onally run a small consola on bracket among late losers to determine posi ons 3..k.

Complexity: trivial arithme c to compute max matches; actual bracket scheduling is O(n).

Egg drop with k eggs & n floors (op mal trials)

Problem. Given k eggs and n floors, what is the minimum number of trials in worst case to find
highest safe floor?

Op mal strategy / DP trick.

Use DP on moves: let dp[m][e] = maximum number of floors that can be tested with m moves and e
eggs. Recurrence:

dp[m][e] = dp[m-1][e-1] + dp[m-1][e] + 1

Interpreta on: one move chosen; if egg breaks, you have m-1 moves and e-1 eggs; otherwise m-1
moves and e eggs. Find minimal m such that dp[m][k] >= n.

Java implementa on (efficient)

// File: [Link]

public class EggDropDP {

 // returns minimal moves m needed

public sta c int superEggDrop(int k, int n) {

// dp[e] for current move m

long[] dp = new long[k + 1];

int m = 0;

while (dp[k] < n) {

m++;

for (int e = k; e >= 1; e--) {

dp[e] = dp[e] + dp[e - 1] + 1; // dp[m][e] = dp[m-1][e] + dp[m-1][e-1] + 1

if (m > n) break; // safety

return m;

public sta c void main(String[] args) {

[Link]("k=2 n=100 -> moves: " + superEggDrop(2, 100)); // classic ~14

[Link]("k=3 n=1000 -> moves: " + superEggDrop(3, 1000));

Complexity: Each move itera on takes O(k) and the number of moves m is typically small (O(log n)
for large k, and O(sqrt(n)) for k=2). So overall roughly O(k * m).

Bridge crossing puzzle (op mal crossing me)

Problem. n people with mes t1..tn must cross a bridge two at a me (flashlight must be carried).
When two cross, me = max(their mes). Minimize total crossing me.

Approach.

 For small n (≤ 15–20) you can get the op mal solu on by DP over subsets (bitmask DP).

 For the common 4-person case, there are well-known greedy pa erns.

Bitmask DP (exact op mal, O(2^n * n^2))

// File: [Link]
import java.u l.*;

public class BridgeCrossingDP {

// mes array length n <= ~16 (2^n manageable)

public sta c int minTime(int[] mes) {

int n = [Link];

int N = 1 << n;

int INF = 1_000_000_000;

int[] dp = new int[N];

Arrays.fill(dp, INF);

dp[0] = 0; // none crossed

// Precompute pair cost (when two or one cross)

int[] cost = new int[N];

for (int mask = 0; mask < N; mask++) {

int max = 0;

int bits = [Link](mask);

if (bits == 0) { cost[mask] = 0; con nue; }

// cost is max me among people in mask (they cross together)

for (int i = 0; i < n; i++) if ((mask & (1<<i)) != 0) max = [Link](max, mes[i]);

cost[mask] = max;

for (int mask = 0; mask < N; mask++) {

// choose subset s of not-yet-crossed to move across (1..n people) but flashlight must come
back unless finishing

int remain = ((N-1) ^ mask);

if (remain == 0) con nue;

// choose subset sub of remain (non-empty)

for (int sub = remain; sub > 0; sub = (sub - 1) & remain) {

int next = mask | sub;

// if next == N-1 (all crossed) -> no return cost

if (next == N-1) dp[next] = [Link](dp[next], dp[mask] + cost[sub]);

 else {

// we must bring flashlight back: choose one person from next to return

for (int ret = 0; ret < n; ret++) {

if ((next & (1<<ret)) != 0) {

int backMask = next ^ (1<<ret); // a er return

dp[backMask] = [Link](dp[backMask], dp[mask] + cost[sub] + mes[ret]);

return dp[N-1];

public sta c void main(String[] args) {

int[] mes = {1,2,7,10}; // classic

[Link]("Min total me: " + minTime( mes)); // expects 17

Complexity: O(2^n * n * 2^n) naïvely; the loop above is roughly O(3^n) if done badly. For n ≤ 15–16
the above is OK. There are op mized DP approaches that restrict sub-selec on to size ≤ 2 (if
flashlight capacity is 2), which reduces complexity greatly.

Domino ling extensions

Problems and variants.

1. Count domino lings of a 2 × n board (classic).

2. Count lings of m × n board with dominoes (harder — use transfer matrix / bitmask DP).

3. Tiling with obstacles / domino lings coun ng mod large prime etc.

Solu ons.

 2 × n lings follow Fibonacci: dp[n] = dp[n-1] + dp[n-2].

 m × n general lings: DP by columns with bitmask state represen ng which cells in a column
are filled/occupied by les from previous column. Standard O(n * 2^m * m) algorithm.
2 × n ling (fibonacci)

// File: [Link]

public class Domino2xn {

public sta c long count2xn(int n) {

if (n == 0) return 1;

if (n == 1) return 1;

long a = 1, b = 1; // dp[0], dp[1]

for (int i = 2; i <= n; i++) {

long c = a + b;

a = b;

b = c;

return b;

public sta c void main(String[] args) {

[Link]("2x5 lings: " + count2xn(5)); // 8

Complexity: O(n).

m × n ling by bitmask DP (skeleton)

// File: [Link]

import java.u l.*;

public class DominoMxN {

// counts lings for m rows and n columns (m small, n larger)

public sta c long countTilings(int m, int n) {

int S = 1 << m;

long[] dp = new long[S], next = new long[S];

dp[0] = 1;

for (int col = 0; col < n; col++) {

Arrays.fill(next, 0);
 for (int mask = 0; mask < S; mask++) {

fillColumn(0, m, mask, 0, dp[mask], next);

long[] tmp = dp; dp = next; next = tmp;

return dp[0];

// recursive fill: mask = occupied cells from previous column; pos = current row; cur = occupancy
we are building for next column

sta c void fillColumn(int pos, int m, int mask, int cur, long ways, long[] next) {

if (ways == 0) return;

if (pos == m) {

next[cur] += ways;

return;

if ((mask & (1<<pos)) != 0) {

fillColumn(pos+1, m, mask, cur, ways, next);

} else {

// place ver cal domino (occupies this cell in this column and same row in next column)

fillColumn(pos+1, m, mask, cur | (1<<pos), ways, next);

// place horizontal domino (covers pos and pos+1 in same column) if possible

if (pos+1 < m && (mask & (1<<(pos+1))) == 0) {

fillColumn(pos+2, m, mask, cur, ways, next);

public sta c void main(String[] args) {

[Link]("Count 3x3 lings (0 expected): " + countTilings(3,3));

[Link]("Count 2x5 lings: " + countTilings(2,5)); // 8

 }

Complexity: O(n * 2^m * m).

Mul -jug (water) puzzle (general)

Problem. Given jugs of capaci es c1...cr with unlimited water and emp es, measure exactly T liters
(in any jug), using pours/fills/emp es.

Approach. Model states as r-tuple (v1..vr). Use BFS on state graph. Ac ons: fill jug i, empty jug i, pour
i->j.

Java BFS solver

// File: Mul [Link]

import java.u l.*;

public class Mul JugSolver {

sta c class State {

int[] v;

State(int[] v){ this.v = [Link](); }

@Override public boolean equals(Object o){ return [Link](v, ((State)o).v); }

@Override public int hashCode(){ return [Link](v); }

public sta c List<String> solve(int[] caps, int target) {

int r = [Link];

State start = new State(new int[r]);

Queue<State> q = new ArrayDeque<>();

Map<State, String> parent = new HashMap<>();

[Link](start); [Link](start, null);

State goalState = null;

while (![Link]()) {

State s = [Link]();

for (int x : s.v) if (x == target) { goalState = s; break; }

 if (goalState != null) break;

// ac ons

// fill i

for (int i = 0; i < r; i++) {

State t = new State(s.v); t.v[i] = caps[i];

if () { [Link](t, "fill " + i); [Link](t); }

// empty i

for (int i = 0; i < r; i++) {

State t = new State(s.v); t.v[i] = 0;

if () { [Link](t, "empty " + i); [Link](t); }

// pour i->j

for (int i = 0; i < r; i++) for (int j = 0; j < r; j++) if (i!=j) {

int[] nv = [Link]();

int amount = [Link](nv[i], caps[j] - nv[j]);

if (amount == 0) con nue;

nv[i] -= amount; nv[j] += amount;

State t = new State(nv);

if () { [Link](t, "pour " + i + "->" + j); [Link](t); }

if (goalState == null) return null; // unsolvable

// reconstruct path (we didn't store predecessor states for brevity)

List<String> path = new ArrayList<>();

[Link]("Found a state with target - state: " + [Link](goalState.v));

return path;

public sta c void main(String[] args) {

int[] caps = {8,5,3};

 [Link](solve(caps, 4));

Complexity: State space size is ∏ (ci + 1); BFS is O(state_count * r^2) due to pours.

Wolf–goat–cabbage (river crossing)

Problem. Farmer must transport wolf, goat, cabbage across a river. Boat holds farmer + at most one
of the other three. Wolf eats goat if farmer not present; goat eats cabbage if farmer not present. Find
safe sequence.

Approach. Very small state graph (2^4 = 16 states). BFS or hand-cra ed solu on. Known solu on
exists.

Java BFS solver

// File: [Link]

import java.u l.*;

public class WolfGoatCabbage {

// state bits: bit0 = farmer side (0 le ,1 right), bit1=wolf, bit2=goat, bit3=cabbage

sta c boolean unsafe(int state) {

int farmer = (state>>0)&1;

int wolf = (state>>1)&1;

int goat = (state>>2)&1;

int cab = (state>>3)&1;

// if farmer not with wolf & goat on same side -> goat eaten

if (wolf == goat && farmer != goat) return true;

// if farmer not with goat & cabbage on same side -> cabbage eaten

if (goat == cab && farmer != goat) return true;

return false;

public sta c List<Integer> solve() {

int start = 0; // all le (0)

int goal = 15; // all right (1)

Queue<Integer> q = new ArrayDeque<>();

[Link](start);
 Map<Integer,Integer> parent = new HashMap<>();

[Link](start, -1);

while (![Link]()) {

int s = [Link]();

if (s == goal) break;

int farmer = (s>>0)&1;

// possible moves: farmer moves alone, or with wolf/goat/cabbage on same side

List<Integer> moves = new ArrayList<>();

// farmer alone

[Link](s ^ 1); // flip farmer bit

// with each of the 3 items i=1..3

for (int i = 1; i <= 3; i++) {

if (((s>>i)&1) == farmer) [Link](s ^ (1<<0) ^ (1<<i));

for (int t : moves) {

if (!unsafe(t) && ) {

[Link](t, s);

[Link](t);

if () return null;

List<Integer> path = new ArrayList<>();

int cur = goal;

while (cur != -1) { [Link](cur); cur = [Link](cur); }

Collec [Link](path);

return path;

sta c String decode(int state) {

String[] names = {"Farmer","Wolf","Goat","Cab"};

 StringBuilder sb = new StringBuilder();

[Link]("[");

for (int i=0;i<4;i++){

[Link](((state>>i)&1)==1 ? names[i]+"(R)" : names[i]+"(L)");

if (i<3) [Link](", ");

[Link]("]");

return [Link]();

public sta c void main(String[] args) {

List<Integer> sol = solve();

for (int s : sol) [Link](decode(s));

Complexity: constant- me (very small state space).

Advanced Josephus problem variant

Problem (classic). n people numbered 0..n-1 stand in a circle. Every k-th person is eliminated; find
survivor.
Variants (advanced): k changes per round (k1, k2, ...), or mul ple elimina ons at once.

Classic recurrence.

J(1,k) = 0

J(n,k) = (J(n-1,k) + k) % n

This yields the survivor index in O(n).

Variant: variable step-per-round. If k changes by round you can simulate removal using order-
sta s cs or linked list simula on. For moderate n you can simulate in O(n log n) with a Fenwick tree
to find k-th alive quickly.

Java: classic & variable-step (Fenwick tree approach)

// File: [Link]

import java.u l.*;

public class JosephusVariants {

// classic O(n)

public sta c int josephusClassic(int n, int k) {

int res = 0;

for (int i = 2; i <= n; i++) res = (res + k) % i;

return res;

// variable steps ks[], ks length >= n-1; we eliminate using a list (O(n^2)) or Fenwick for O(n log n).

// Here a simple O(n) simula on using ArrayList (ok for n up to ~5e4)

public sta c int josephusVariable(int n, int[] ks) {

List<Integer> people = new ArrayList<>();

for (int i = 0; i < n; i++) [Link](i);

int idx = 0;

int round = 0;

while ([Link]() > 1) {

int k = ks[[Link](round, [Link]-1)];

idx = (idx + k - 1) % [Link]();

[Link](idx);

round++;

return [Link](0);

public sta c void main(String[] args) {

[Link]("Classic n=7 k=3 -> survivor: " + josephusClassic(7,3)); // 3

int[] ks = {3,2,5,1,3,2};

[Link]("Variable-step survivor: " + josephusVariable(7, ks));

Complexity: classic O(n); naive variable-step O(n^2) worst-case (ArrayList removals). Using a Fenwick
tree or order-stat tree yields O(n log n).