Arrays, Strings, Linked Lists,

Stacks & Queues

Java Solutions with Detailed Explanatory Comments

15 Classic Data Structure & Algorithm Problems

Single-file Java implementation: [Link]
Table of Contents

1 Prefix Sum Array

2 Equilibrium Index

3 Two Sum (Sorted Array) — Two Pointer

4 Majority Element — Boyer-Moore Voting

5 Counting Bits (0 to n)

6 Power of Two — Bit Manipulation

7 Trapping Rain Water

8 Longest Palindromic Substring

9 Longest Common Prefix

10 Merge Two Sorted Linked Lists

11 Intersection of Two Linked Lists

12 Two Stacks in a Single Array

13 Next Greater Element — Monotonic Stack

14 Largest Rectangle in Histogram

15 Sliding Window Maximum — Deque

[Link] — Full Source Code
1 import [Link].*;
2
3 /**
4 * ============================================================
* ARRAYS, STRINGS, LINKED LISTS, STACKS & QUEUES - JAVA SOLUTIONS
5
* ============================================================
6
* This file contains Java solutions for 15 classic data
7 * structure & algorithm problems. Each problem has its own
8 * static method with detailed comments explaining the logic,
9 * along with its time and space complexity.
10 * ============================================================
11 */
12 public class Solutions {
13
14 // ============================================================
15 // 1. PREFIX SUM ARRAY
// ------------------------------------------------------------
16
// Build a prefix sum array where prefix[i] = sum of arr[0..i-1].
17
// Then sum of range [L, R] (inclusive) = prefix[R+1] - prefix[L].
18 // This allows O(1) range-sum queries after an O(n) pre-processing step.
19 // Time: O(n) to build, O(1) per query | Space: O(n)
20 // ============================================================
21 static int[] buildPrefixSum(int[] arr) {
22 // prefix[0] = 0 acts as a base case so prefix[i+1] - prefix[L] works
23 // even when L = 0, avoiding extra boundary checks.
24 int[] prefix = new int[[Link] + 1];
25 for (int i = 0; i < [Link]; i++) {
26 // Each prefix value accumulates the sum so far.
prefix[i + 1] = prefix[i] + arr[i];
27
}
28
return prefix;
29 }
30
31 static int rangeSum(int[] prefix, int L, int R) {
32 // Sum of elements between indices L and R inclusive.
33 return prefix[R + 1] - prefix[L];
34 }
35
36
37 // ============================================================
// 2. EQUILIBRIUM INDEX
38
// ------------------------------------------------------------
39
// An equilibrium index is an index where the sum of elements
40 // to its left equals the sum of elements to its right.
41 // We precompute the total sum, then walk through the array
42 // tracking the running left sum; right sum = total - left - arr[i].
43 // Time: O(n) | Space: O(1)
44 // ============================================================
45 static int equilibriumIndex(int[] arr) {
46 int totalSum = 0;
47 for (int num : arr) totalSum += num;
48
int leftSum = 0;
49
for (int i = 0; i < [Link]; i++) {
50
// Right sum = everything left over after removing leftSum and arr[i].
51 int rightSum = totalSum - leftSum - arr[i];
52 if (leftSum == rightSum) {
53 return i; // Found the equilibrium index.
54 }
55 // Update running left sum for the next iteration.
56 leftSum += arr[i];
57 }
58 return -1; // No equilibrium index found.
59 }
60
61
// ============================================================
62 // 3. TWO SUM (SORTED ARRAY) - TWO POINTER TECHNIQUE
63 // ------------------------------------------------------------
64 // Since the array is already sorted, we can use two pointers:
65 // one starting from the left (smallest) and one from the right
66 // (largest). Move them inward based on comparison with target.
67 // Time: O(n) | Space: O(1)
68 // ============================================================
69 static int[] twoSumSorted(int[] arr, int target) {
70 int left = 0, right = [Link] - 1;
71
while (left < right) {
72
int sum = arr[left] + arr[right];
73 if (sum == target) {
74 return new int[]{left, right}; // Found the pair.
75 } else if (sum < target) {
76 left++; // Need a bigger sum, move left pointer right.
77 } else {
78 right--; // Need a smaller sum, move right pointer left.
79 }
80 }
81 return new int[]{-1, -1}; // No pair found.
}
82
83
84 // ============================================================
85 // 4. MAJORITY ELEMENT - BOYER-MOORE VOTING ALGORITHM
86 // ------------------------------------------------------------
87 // The majority element appears more than n/2 times. Boyer-Moore
88 // voting cancels out one majority vote with one non-majority
89 // vote; whatever survives at the end is the majority element.
90 // Time: O(n) | Space: O(1)
91 // ============================================================
92 static int majorityElement(int[] arr) {
int candidate = arr[0];
93
int count = 0;
94
95 for (int num : arr) {
96 if (num == candidate) {
97 count++; // Vote for the current candidate.
98 } else {
99 count--; // Cancel out a vote.
100 }
101 // If votes drop to zero, switch to a new candidate.
102 if (count == 0) {
103 candidate = num;
count = 1;
104
}
105
}
106 return candidate; // Guaranteed majority element if one exists.
107 }
108
109
110 // ============================================================
111 // 5. COUNTING BITS (0 to n)
112 // ------------------------------------------------------------
113 // For each number i, the count of set bits equals the count of
114 // set bits in (i >> 1) [i.e., i divided by 2] plus 1 if i is odd
115 // (i.e., the last bit i & 1). This is a classic DP-on-bits trick.
116 // Time: O(n) | Space: O(n)
// ============================================================
117
static int[] countBits(int n) {
118
int[] result = new int[n + 1];
119 for (int i = 1; i <= n; i++) {
120 // result[i >> 1] = bit count of i with the last bit removed.
121 // (i & 1) adds 1 back if the last bit is set (i is odd).
122 result[i] = result[i >> 1] + (i & 1);
123 }
124 return result;
125 }
126
127
// ============================================================
128
// 6. POWER OF TWO - BIT MANIPULATION
129
// ------------------------------------------------------------
130 // A power of two has exactly ONE bit set in binary (e.g. 8 = 1000).
131 // The trick: n & (n - 1) clears the lowest set bit. If n is a
132 // power of two, this operation results in 0.
133 // Time: O(1) | Space: O(1)
134 // ============================================================
135 static boolean isPowerOfTwo(int n) {
136 // Must be positive, and clearing the lowest set bit gives 0
137 // only when there was exactly one bit set originally.
138 return n > 0 && (n & (n - 1)) == 0;
}
139
140
141 // ============================================================
142 // 7. TRAPPING RAIN WATER
143 // ------------------------------------------------------------
144 // Water trapped above bar i is limited by the shorter of the
145 // tallest bar to its left and the tallest bar to its right,
146 // minus the bar's own height. We use two pointers moving inward,
147 // always advancing the side with the smaller "max so far" since
148 // that side determines the water level at the current position.
149 // Time: O(n) | Space: O(1)
// ============================================================
150
static int trapRainWater(int[] height) {
151
if ([Link] == 0) return 0;
152
153 int left = 0, right = [Link] - 1;
154 int leftMax = 0, rightMax = 0;
155 int totalWater = 0;
156
157 while (left < right) {
158 if (height[left] < height[right]) {
159 // Left side is the limiting (shorter) wall.
160 if (height[left] >= leftMax) {
leftMax = height[left]; // Update tallest seen on left.
161
} else {
162
// Water trapped = difference between leftMax and current bar.
163 totalWater += leftMax - height[left];
164 }
165 left++;
166 } else {
167 // Right side is the limiting (shorter or equal) wall.
168 if (height[right] >= rightMax) {
169 rightMax = height[right]; // Update tallest seen on right.
170 } else {
171 totalWater += rightMax - height[right];
}
172
right--;
173
}
174 }
175 return totalWater;
176 }
177
178
179 // ============================================================
180 // 8. LONGEST PALINDROMIC SUBSTRING - EXPAND AROUND CENTER
181 // ------------------------------------------------------------
182 // Every palindrome mirrors around its center. A palindrome can
// have an odd length (single center character) or even length
183
// (center between two characters). We try both center types for
184
// every index and expand outward while characters match.
185 // Time: O(n^2) | Space: O(1)
186 // ============================================================
187 static String longestPalindrome(String s) {
188 if (s == null || [Link]() == 0) return "";
189
190 int start = 0, maxLength = 0;
191
192 for (int center = 0; center < [Link](); center++) {
193 // Odd-length palindromes: center is a single character.
int len1 = expandAroundCenter(s, center, center);
194
// Even-length palindromes: center is between two characters.
195
int len2 = expandAroundCenter(s, center, center + 1);
196
197 int currentMax = [Link](len1, len2);
198 if (currentMax > maxLength) {
199 maxLength = currentMax;
200 // Recompute the starting index of this palindrome.
201 start = center - (currentMax - 1) / 2;
202 }
203 }
204 return [Link](start, start + maxLength);
}
205
206
// Helper: expands outward from a center pair (left, right) as long
207 // as characters match, and returns the length of that palindrome.
208 static int expandAroundCenter(String s, int left, int right) {
209 while (left >= 0 && right < [Link]() && [Link](left) == [Link](right)) {
210 left--;
211 right++;
212 }
213 // Loop overshoots by one step on both sides, so subtract back.
214 return right - left - 1;
215 }
216
217
// ============================================================
218 // 9. LONGEST COMMON PREFIX
219 // ------------------------------------------------------------
220 // Take the first string as a reference prefix candidate. Compare
221 // it character-by-character against every other string, shrinking
222 // the candidate prefix whenever a mismatch (or string-end) occurs.
223 // Time: O(n*m) where n = number of strings, m = length of shortest string
224 // Space: O(1) extra (ignoring the returned string)
225 // ============================================================
226 static String longestCommonPrefix(String[] strs) {
if (strs == null || [Link] == 0) return "";
227
228
String prefix = strs[0]; // Start with the first string as a guess.
229
230 for (int i = 1; i < [Link]; i++) {
231 // Shrink prefix until it matches the start of strs[i].
232 while (!strs[i].startsWith(prefix)) {
233 prefix = [Link](0, [Link]() - 1);
234 if ([Link]()) return ""; // No common prefix at all.
}
235
}
236
return prefix;
237 }
238
239
240 // ============================================================
241 // 10. MERGE TWO SORTED LINKED LISTS
242 // ------------------------------------------------------------
243 // Use a dummy head node to simplify edge cases. Compare the
244 // current nodes of both lists, attach the smaller one to the
245 // merged list, and advance that list's pointer. Continue until
// one list is exhausted, then attach the remainder of the other.
246
// Time: O(n + m) | Space: O(1) extra (excluding output nodes)
247
// ============================================================
248 static class ListNode {
249 int val;
250 ListNode next;
251 ListNode(int val) { [Link] = val; }
252 }
253
254 static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
255 // Dummy node lets us avoid special-casing the very first node.
256 ListNode dummy = new ListNode(0);
ListNode tail = dummy;
257
258
while (l1 != null && l2 != null) {
259 if ([Link] <= [Link]) {
260 [Link] = l1; // Attach smaller node.
261 l1 = [Link];
262 } else {
263 [Link] = l2;
264 l2 = [Link];
265 }
266 tail = [Link]; // Move tail forward.
267 }
268
// Attach whichever list still has remaining nodes.
269
[Link] = (l1 != null) ? l1 : l2;
270
271 return [Link]; // Skip the dummy head.
272 }
273
274
275 // ============================================================
276 // 11. INTERSECTION OF TWO LINKED LISTS
277 // ------------------------------------------------------------
278 // Use two pointers, one for each list. When a pointer reaches
// the end of its list, redirect it to the HEAD of the OTHER list.
279
// Because of this "switch", both pointers travel the same total
280
// distance (lenA + lenB), so they are guaranteed to meet exactly
281 // at the intersection node (or both become null if no intersection).
282 // Time: O(n + m) | Space: O(1)
283 // ============================================================
284 static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
285 if (headA == null || headB == null) return null;
286
287 ListNode pointerA = headA;
288 ListNode pointerB = headB;
289
// They will meet after traveling equal total distances.
290
while (pointerA != pointerB) {
291
// If pointerA hits the end, redirect it to headB; else advance.
292 pointerA = (pointerA == null) ? headB : [Link];
293 // If pointerB hits the end, redirect it to headA; else advance.
294 pointerB = (pointerB == null) ? headA : [Link];
295 }
296 // Either the intersection node, or null if lists never intersect.
297 return pointerA;
298 }
299
300
// ============================================================
301
// 12. TWO STACKS IN A SINGLE ARRAY
302
// ------------------------------------------------------------
303 // Stack 1 grows from the LEFT end (index 0) moving rightward.
304 // Stack 2 grows from the RIGHT end (last index) moving leftward.
305 // As long as top1 < top2, there's still room in the middle,
306 // so both stacks can coexist within a single shared array.
307 // Time: O(1) for push/pop | Space: O(n) shared array
308 // ============================================================
309 static class TwoStacks {
310 int[] arr;
311 int top1; // Points to the top of stack 1 (starts at -1, empty).
int top2; // Points to the top of stack 2 (starts at [Link], empty).
312
313
TwoStacks(int n) {
314 arr = new int[n];
315 top1 = -1;
316 top2 = n;
317 }
318
319 // Push onto stack 1 (grows from the left).
320 void push1(int value) {
321 // Overflow check: stacks would collide in the middle.
322 if (top1 + 1 < top2) {
arr[++top1] = value;
323
} else {
324
[Link]("Stack Overflow (Stack 1)");
325 }
326 }
327
328 // Push onto stack 2 (grows from the right).
329 void push2(int value) {
330 if (top1 + 1 < top2) {
331 arr[--top2] = value;
332 } else {
333 [Link]("Stack Overflow (Stack 2)");
}
334
}
335
336 // Pop from stack 1.
337 int pop1() {
338 if (top1 >= 0) {
339 return arr[top1--];
340 }
341 [Link]("Stack 1 Underflow");
342 return -1;
343 }
344
// Pop from stack 2.
345
int pop2() {
346
if (top2 < [Link]) {
347 return arr[top2++];
348 }
349 [Link]("Stack 2 Underflow");
350 return -1;
351 }
352 }
353
354
// ============================================================
355
// 13. NEXT GREATER ELEMENT - MONOTONIC STACK
356 // ------------------------------------------------------------
357 // Traverse the array from right to left, maintaining a stack
358 // that only holds elements which are bigger than what's below
359 // them (a "monotonic decreasing" stack from bottom to top, when
360 // walking right-to-left). For each element, pop everything
361 // smaller or equal off the stack (they can never be the "next
362 // greater" for anything further left), then the new stack top
363 // (if any) is the next greater element. Finally push current.
364 // Time: O(n) | Space: O(n)
// ============================================================
365
static int[] nextGreaterElement(int[] arr) {
366
int n = [Link];
367 int[] result = new int[n];
368 Deque<Integer> stack = new ArrayDeque<>(); // Holds candidate values.
369
370 for (int i = n - 1; i >= 0; i--) {
371 // Remove all stack elements that are <= current element;
372 // they cannot be "next greater" for arr[i] or anything before it.
373 while (![Link]() && [Link]() <= arr[i]) {
374 [Link]();
375 }
// Whatever remains on top (if anything) is the next greater element.
376
result[i] = [Link]() ? -1 : [Link]();
377
378 // Push current element so it can be considered for elements to its left.
379 [Link](arr[i]);
380 }
381 return result;
382 }
383
384
385 // ============================================================
386 // 14. LARGEST RECTANGLE IN HISTOGRAM - MONOTONIC STACK
// ------------------------------------------------------------
387
// For every bar, the largest rectangle using that bar as the
388
// height extends as far left and right as neighboring bars are
389 // >= its height. We use a stack of indices with increasing bar
390 // heights. When we find a bar shorter than the stack's top, the
391 // top bar can't extend further right, so we "close" it: pop it
392 // and compute its max rectangle area using the current index as
393 // the right boundary and the new stack top as the left boundary.
394 // Time: O(n) | Space: O(n)
395 // ============================================================
396 static int largestRectangleArea(int[] heights) {
397 Deque<Integer> stack = new ArrayDeque<>(); // Stores indices.
int maxArea = 0;
398
int n = [Link];
399
400 for (int i = 0; i <= n; i++) {
401 // Treat index n as having height 0 to flush remaining bars.
402 int currentHeight = (i == n) ? 0 : heights[i];
403
404 // While current bar is shorter than the bar at stack's top,
405 // that top bar's rectangle is fully determined - compute it.
406 while (![Link]() && currentHeight < heights[[Link]()]) {
407 int height = heights[[Link]()];
408 // Width: from the element after new stack top, to i-1.
// If stack becomes empty, the rectangle spans from index 0.
409
int width = [Link]() ? i : i - [Link]() - 1;
410
maxArea = [Link](maxArea, height * width);
411 }
412 [Link](i); // Current bar might extend rectangles to the right.
413 }
414 return maxArea;
415 }
416
417
418 // ============================================================
419 // 15. SLIDING WINDOW MAXIMUM - DEQUE
// ------------------------------------------------------------
420
// Maintain a deque of INDICES such that the values at those
421
// indices are in decreasing order from front to back. The front
422 // of the deque is always the maximum of the current window.
423 // - Remove indices from the front that have fallen out of the
424 // current window (i.e., index <= i - k).
425 // - Remove indices from the back whose values are smaller than
426 // the current element (they can never be the max while the
427 // current, more competitive element is still in the window).
428 // Time: O(n) - each element is pushed/popped at most once | Space: O(k)
429 // ============================================================
430 static int[] maxSlidingWindow(int[] nums, int k) {
int n = [Link];
431
if (n == 0 || k <= 0) return new int[0];
432
433 int[] result = new int[n - k + 1];
434 Deque<Integer> deque = new ArrayDeque<>(); // Stores indices.
435
436 for (int i = 0; i < n; i++) {
437 // Remove indices that are out of the current window's left bound.
438 while (![Link]() && [Link]() <= i - k) {
439 [Link]();
440 }
441 // Remove indices whose values are smaller than nums[i];
// they're useless since nums[i] is both newer and bigger.
442
while (![Link]() && nums[[Link]()] < nums[i]) {
443
[Link]();
444 }
445 // Add current index as a candidate for future windows.
446 [Link](i);
447
448 // Once the first window is complete, record the max (front of deque).
449 if (i >= k - 1) {
450 result[i - k + 1] = nums[[Link]()];
451 }
452 }
return result;
453
}
454
455
456 // ============================================================
457 // MAIN METHOD - DEMONSTRATES EACH SOLUTION WITH SAMPLE INPUT
458 // ============================================================
459 public static void main(String[] args) {
460
461 [Link]("1. Prefix Sum Array");
462 int[] arr1 = {2, 4, 6, 8, 10};
463 int[] prefix = buildPrefixSum(arr1);
[Link]("Array: " + [Link](arr1));
464
[Link]("Sum of range [1, 3]: " + rangeSum(prefix, 1, 3));
465
[Link]();
466
467 [Link]("2. Equilibrium Index");
468 int[] arr2 = {-7, 1, 5, 2, -4, 3, 0};
469 [Link]("Array: " + [Link](arr2));
470 [Link]("Equilibrium Index: " + equilibriumIndex(arr2));
[Link]();
471
472
[Link]("3. Two Sum (Sorted Array)");
473 int[] arr3 = {1, 2, 4, 6, 10};
474 int[] indices = twoSumSorted(arr3, 8);
475 [Link]("Array: " + [Link](arr3) + ", Target: 8");
476 [Link]("Indices: " + [Link](indices));
477 [Link]();
478
479 [Link]("4. Majority Element");
480 int[] arr4 = {2, 2, 1, 1, 1, 2, 2};
481 [Link]("Array: " + [Link](arr4));
[Link]("Majority Element: " + majorityElement(arr4));
482
[Link]();
483
484 [Link]("5. Counting Bits");
485 int n5 = 5;
486 [Link]("n = " + n5);
487 [Link]("Bit Counts: " + [Link](countBits(n5)));
488 [Link]();
489
490 [Link]("6. Power of Two");
491 int[] testValues = {1, 16, 18, 64, 100};
492 for (int val : testValues) {
[Link](val + " is power of two: " + isPowerOfTwo(val));
493
}
494
[Link]();
495
496 [Link]("7. Trapping Rain Water");
497 int[] heights7 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
498 [Link]("Heights: " + [Link](heights7));
499 [Link]("Water Trapped: " + trapRainWater(heights7));
500 [Link]();
501
502 [Link]("8. Longest Palindromic Substring");
503 String s8 = "babad";
[Link]("String: " + s8);
504
[Link]("Longest Palindrome: " + longestPalindrome(s8));
505
[Link]();
506
507 [Link]("9. Longest Common Prefix");
508 String[] strs9 = {"flower", "flow", "flight"};
509 [Link]("Strings: " + [Link](strs9));
510 [Link]("Longest Common Prefix: \"" + longestCommonPrefix(strs9) + "\"");
511 [Link]();
512
513 [Link]("10. Merge Two Sorted Linked Lists");
514 ListNode l1 = new ListNode(1);
[Link] = new ListNode(3);
515
[Link] = new ListNode(5);
516
ListNode l2 = new ListNode(2);
517 [Link] = new ListNode(4);
518 [Link] = new ListNode(6);
519 ListNode merged = mergeTwoLists(l1, l2);
520 [Link]("Merged List: ");
521 printList(merged);
522 [Link]();
523
524 [Link]("11. Intersection of Two Linked Lists");
525 ListNode common = new ListNode(8);
[Link] = new ListNode(10);
526
ListNode headA = new ListNode(3);
527
[Link] = new ListNode(7);
528 [Link] = common;
529 ListNode headB = new ListNode(99);
530 [Link] = common;
531 ListNode intersection = getIntersectionNode(headA, headB);
532 [Link]("Intersection Node Value: " +
533 (intersection != null ? [Link] : "None"));
534 [Link]();
535
536 [Link]("12. Two Stacks in a Single Array");
TwoStacks ts = new TwoStacks(10);
537
ts.push1(1);
538
ts.push1(2);
539 ts.push1(3);
540 ts.push2(100);
541 ts.push2(200);
542 [Link]("Popped from Stack 1: " + ts.pop1());
543 [Link]("Popped from Stack 2: " + ts.pop2());
544 [Link]();
545
546 [Link]("13. Next Greater Element");
547 int[] arr13 = {4, 5, 2, 25};
[Link]("Array: " + [Link](arr13));
548
[Link]("Next Greater Elements: " + [Link](nextGreaterElement(arr13)));
549
[Link]();
550
551 [Link]("14. Largest Rectangle in Histogram");
552 int[] heights14 = {2, 1, 5, 6, 2, 3};
553 [Link]("Heights: " + [Link](heights14));
554 [Link]("Largest Rectangle Area: " + largestRectangleArea(heights14));
555 [Link]();
556
557 [Link]("15. Sliding Window Maximum");
558 int[] nums15 = {1, 3, -1, -3, 5, 3, 6, 7};
int k15 = 3;
559
[Link]("Array: " + [Link](nums15) + ", k = " + k15);
560
[Link]("Sliding Window Maximums: " + [Link](maxSlidingWindow(nums15, k15)));
561 }
562
563 // Helper method to print a linked list.
564 static void printList(ListNode head) {
565 ListNode curr = head;
566 while (curr != null) {
567 [Link]([Link]);
568 if ([Link] != null) [Link](" -> ");
569 curr = [Link];
}
570
[Link]();
571
}
572 }
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625