Data Structures Syntax & Formula Reference
Quick-lookup sheet - one page per pattern. Code in Java.
1. Bit Manipulation
Binary Representation
[Link](n); // no leading zeros
[Link]("%8s", [Link](n)).replace(' ', '0'); // zero-padded to 8 bits
Power of 2 check
A power of 2 has exactly one set bit. n & (n-1) clears the lowest set bit.
static boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
Finding Missing Number (0..n)
XOR of all numbers 0..n XOR all array elements. Pairs cancel, missing number remains.
static int missingNumber(int[] arr, int n) {
int x = 0;
for (int i = 0; i <= n; i++) x ^= i;
for (int v : arr) x ^= v;
return x;
}
Count Set Bits
[Link](n); // built-in
// or Brian Kernighan's:
static int countBits(int n) {
int c = 0;
while (n != 0) {
n &= (n - 1);
c++;
}
return c;
}
X 1s and Y 0s / X and Y set bits (construction)
Build number bit by bit: start from MSB, set bits with a left-shift OR operation, leave rest 0. To place X ones then Y zeros:
shift a block of X ones left by Y.
static int xOnesYZeros(int x, int y) {
int onesBlock = (1 << x) - 1; // x ones
return onesBlock << y; // shifted left by y zero-bits
}
Flip Bits
static int flip(int n, int bits) {
int mask = (1 << bits) - 1;
return n ^ mask; // XOR with all-1s mask flips every bit
}
Reverse Bits
static int reverseBits(int n, int bits) {
int result = 0;
for (int i = 0; i < bits; i++) {
result |= ((n >> i) & 1) << (bits - 1 - i);
}
return result;
}
Swap Bits (positions i, j)
static int swapBits(int n, int i, int j) {
int bi = (n >> i) & 1;
int bj = (n >> j) & 1;
if (bi != bj) {
n ^= (1 << i) | (1 << j); // toggle both if different
}
return n;
}
A power B (fast exponentiation)
static long power(long a, long b, long mod) {
long result = 1;
a %= mod;
while (b > 0) {
if ((b & 1) == 1) result = (result * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return result;
}
Triple Trouble / Repeated Numbers (Hashmap)
Use a HashMap to track frequency; for 'exactly one appears twice' patterns, XOR still works if others appear an even
number of times.
Map<Integer, Integer> freq = new HashMap<>();
for (int v : arr) [Link](v, 1, Integer::sum);
for ([Link]<Integer, Integer> e : [Link]()) {
if ([Link]() != expectedCount) return [Link]();
}
XOR of Sum of Pairs / Product of XOR of Pairs
Expand pair-wise operations combinatorially. For XOR of (a_i + a_j) over all pairs i before j: bit-by-bit contribution counting
is often faster than brute force O(n^2).
// Brute force base case:
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
result ^= (arr[i] + arr[j]); // or arr[i] ^ arr[j] depending on question
}
}
2. Sorting & Two Pointers
Bubble Sort - O(n^2)
static void bubbleSort(int[] a) {
int n = [Link];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
}
}
Selection Sort - O(n^2)
static void selectionSort(int[] a) {
int n = [Link];
for (int i = 0; i < n; i++) {
int m = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[m]) m = j;
}
int t = a[i]; a[i] = a[m]; a[m] = t;
}
}
Insertion Sort - O(n^2), good for nearly-sorted
static void insertionSort(int[] a) {
for (int i = 1; i < [Link]; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]; j--;
}
a[j + 1] = key;
}
}
Sort 0s and 1s (Dutch flag, 2-way)
static void sort01(int[] a) {
int l = 0, r = [Link] - 1;
while (l < r) {
if (a[l] == 0) l++;
else if (a[r] == 1) r--;
else {
int t = a[l]; a[l] = a[r]; a[r] = t;
}
}
}
Smaller Elements / Sum of Pairs / Pair with Difference K
Sort first, then use two pointers from both ends, or a HashSet for O(n) difference lookups.
// Pair with difference K (sorted array, two pointer):
static int[] pairDiffK(int[] a, int k) {
[Link](a);
int i = 0, j = 1;
while (j < [Link]) {
int d = a[j] - a[i];
if (d == k && i != j) return new int[]{a[i], a[j]};
else if (d < k) j++;
else i++;
}
return null;
}
Triplet with Sum K
static int[] tripletSum(int[] a, int k) {
[Link](a);
int n = [Link];
for (int i = 0; i < n - 2; i++) {
int l = i + 1, r = n - 1;
while (l < r) {
int s = a[i] + a[l] + a[r];
if (s == k) return new int[]{a[i], a[l], a[r]};
else if (s < k) l++;
else r--;
}
}
return null;
}
Count the Triangles (sorted + 2ptr)
static int countTriangles(int[] a) {
[Link](a);
int n = [Link], count = 0;
for (int k = n - 1; k > 1; k--) {
int i = 0, j = k - 1;
while (i < j) {
if (a[i] + a[j] > a[k]) {
count += (j - i); j--;
} else {
i++;
}
}
}
return count;
}
Frequency Sort
static Integer[] freqSort(int[] a) {
Map<Integer, Integer> freq = new HashMap<>();
for (int v : a) [Link](v, 1, Integer::sum);
Integer[] boxed = [Link](a).boxed().toArray(Integer[]::new);
[Link](boxed, (x, y) -> [Link](y) - [Link](x));
return boxed;
}
3. Searching
Finding the Floor (largest element <= target, sorted array)
static int floor(int[] a, int target) {
int lo = 0, hi = [Link] - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] <= target) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}
return ans;
}
Finding CubeRoot (binary search on answer)
static int cubeRoot(int n) {
int lo = 0, hi = n;
while (lo <= hi) {
int mid = (lo + hi) / 2;
long cube = (long) mid * mid * mid;
if (cube == n) return mid;
else if (cube < n) lo = mid + 1;
else hi = mid - 1;
}
return hi; // closest floor value
}
Finding Frequency (of an element in sorted array)
Binary search for first and last occurrence separately; frequency = last - first + 1.
static int firstOccurrence(int[] a, int x) {
int lo = 0, hi = [Link] - 1, res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] == x) { res = mid; hi = mid - 1; }
else if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return res;
}
4. Subarrays & Subsequences
Maximum Contiguous Subsequence (Kadane's Algorithm)
static int maxSubarray(int[] a) {
int curr = a[0], best = a[0];
for (int i = 1; i < [Link]; i++) {
curr = [Link](a[i], curr + a[i]);
best = [Link](best, curr);
}
return best;
}
Rearrange Sequence (1/2/3 variants)
Common patterns: alternate positive/negative (two-pointer with extra array), rearrange into a zig-zag order where each
element alternately dips below and rises above its neighbors, or rotate in place. Zig-zag trick below.
static void zigzag(int[] a) {
for (int i = 0; i < [Link] - 1; i++) {
boolean shouldSwap = (i % 2 == 0 && a[i] > a[i + 1]) ||
(i % 2 == 1 && a[i] < a[i + 1]);
if (shouldSwap) {
int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
}
}
}
Non-Decreasing Subarrays (longest run)
static int longestNonDecreasing(int[] a) {
int best = 1, curr = 1;
for (int i = 1; i < [Link]; i++) {
curr = (a[i] >= a[i - 1]) ? curr + 1 : 1;
best = [Link](best, curr);
}
return best;
}
Sum of all Subarrays / Sum of Subarrays
Each element a[i] appears in (i+1) * (n-i) subarrays. Use this contribution formula instead of generating every subarray
(O(n) vs O(n^2)).
static long sumOfAllSubarrays(int[] a) {
int n = [Link];
long total = 0;
for (int i = 0; i < n; i++) {
total += (long) a[i] * (i + 1) * (n - i);
}
return total;
}
Distinct Elements in Window (sliding window + hashmap)
static List<Integer> distinctInWindows(int[] a, int k) {
Map<Integer, Integer> freq = new HashMap<>();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < [Link]; i++) {
[Link](a[i], 1, Integer::sum);
if (i >= k) {
int out = a[i - k];
[Link](out, [Link](out) - 1);
if ([Link](out) == 0) [Link](out);
}
if (i >= k - 1) [Link]([Link]());
}
return res;
}
Query Odd Sum (prefix sum)
static int[] prefixSum(int[] a) {
int[] p = new int[[Link] + 1];
for (int i = 0; i < [Link]; i++) p[i + 1] = p[i] + a[i];
return p;
}
// range sum(l, r) inclusive = p[r+1] - p[l]
5. Strings
First Repeating Character (1 & 2)
static Character firstRepeating(String s) {
Set<Character> seen = new HashSet<>();
for (char ch : [Link]()) {
if ([Link](ch)) return ch;
[Link](ch);
}
return null;
}
// Variant: first char whose SECOND occurrence comes earliest
static Character firstRepeatingV2(String s) {
Map<Character, Integer> idx = new HashMap<>();
for (int i = 0; i < [Link](); i++) {
char ch = [Link](i);
if ([Link](ch)) return ch;
[Link](ch, i);
}
return null;
}
Longest Substring without Vowels
static final String VOWELS = "aeiouAEIOU";
static int longestNoVowel(String s) {
int best = 0, curr = 0;
for (char ch : [Link]()) {
if ([Link](ch) == -1) { curr++; best = [Link](best, curr); }
else curr = 0;
}
return best;
}
Number of Monotonous Substrings
A monotonous substring is strictly increasing or decreasing char-code-wise. Count run lengths, sum n*(n+1)/2 style per
run.
static long countMonotonous(String s) {
int n = [Link]();
long total = 0;
int i = 0;
while (i < n) {
int j = i;
while (j + 1 < n && [Link](j + 1) > [Link](j)) j++;
int len = j - i + 1;
total += (long) len * (len + 1) / 2;
i = (j > i) ? j + 1 : i + 1;
}
return total;
}
Words, Vowels and Consonants
static int[] analyze(String s) {
String[] words = [Link]().split("\\s+");
int vowels = 0, consonants = 0;
for (char c : [Link]().toCharArray()) {
if ("aeiou".indexOf(c) != -1) vowels++;
else if ([Link](c)) consonants++;
}
return new int[]{[Link], vowels, consonants};
}
Check Anagrams
static boolean isAnagram(String a, String b) {
char[] ca = [Link](), cb = [Link]();
[Link](ca); [Link](cb);
return [Link](ca, cb);
}
Number of Anagramic Groups
static Collection<List<String>> anagramGroups(String[] words) {
Map<String, List<String>> groups = new HashMap<>();
for (String w : words) {
char[] c = [Link]();
[Link](c);
String key = new String(c);
[Link](key, k -> new ArrayList<>()).add(w);
}
return [Link]();
}
Longest Substring with Max K Vowels (sliding window)
static int longestWithKVowels(String s, int k) {
String vowels = "aeiouAEIOU";
int l = 0, count = 0, best = 0;
for (int r = 0; r < [Link](); r++) {
if ([Link]([Link](r)) != -1) count++;
while (count > k) {
if ([Link]([Link](l)) != -1) count--;
l++;
}
best = [Link](best, r - l + 1);
}
return best;
}
Words Start & End with Vowel
static List<String> vowelWords(String s) {
String vowels = "aeiouAEIOU";
List<String> res = new ArrayList<>();
for (String w : [Link]("\\s+")) {
if ([Link]([Link](0)) != -1 &&
[Link]([Link]([Link]() - 1)) != -1) {
[Link](w);
}
}
return res;
}
6. Stacks & Queues
Implement Stack (array-based)
class Stack {
private int[] a;
private int top = -1;
Stack(int cap) { a = new int[cap]; }
void push(int x) { a[++top] = x; }
int pop() { return top >= 0 ? a[top--] : -1; }
int peek() { return top >= 0 ? a[top] : -1; }
boolean isEmpty() { return top == -1; }
}
// Or simply use [Link]<Integer> as a stack (push/pop/peek).
Reverse the Sentence (using stack)
static String reverseSentence(String s) {
String[] words = [Link]().split("\\s+");
Deque<String> stack = new ArrayDeque<>([Link](words));
StringBuilder sb = new StringBuilder();
while (![Link]()) {
[Link]([Link]());
if (![Link]()) [Link](" ");
}
return [Link]();
}
Collecting Mangoes (stack-based next-greater pattern)
Classic 'next greater element' style: use a monotonic stack to find, for each index, the next element that satisfies a
condition, in O(n).
static int[] nextGreater(int[] a) {
int n = [Link];
int[] res = new int[n];
[Link](res, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (![Link]() && a[[Link]()] < a[i]) {
res[[Link]()] = a[i];
}
[Link](i);
}
return res;
}
Implement Queue (array-based, circular)
class Queue {
private int[] a;
private int front = 0, size = 0, cap;
Queue(int cap) { [Link] = cap; a = new int[cap]; }
void enqueue(int x) {
int idx = (front + size) % cap;
a[idx] = x; size++;
}
int dequeue() {
int x = a[front];
front = (front + 1) % cap; size--;
return x;
}
}
Implement Deque
Deque<Integer> d = new ArrayDeque<>();
[Link](x); // push front
[Link](x); // push back
[Link](); // pop front
[Link](); // pop back
7. Trees
Node Definition
class Node {
int val;
Node left, right;
Node(int val) { [Link] = val; }
}
BST Operations (insert / search)
static Node insert(Node root, int val) {
if (root == null) return new Node(val);
if (val < [Link]) [Link] = insert([Link], val);
else [Link] = insert([Link], val);
return root;
}
static Node search(Node root, int val) {
if (root == null || [Link] == val) return root;
return val < [Link] ? search([Link], val) : search([Link], val);
}
Tree Traversals (in/pre/post-order)
static void inorder(Node r, List<Integer> out) {
if (r == null) return;
inorder([Link], out); [Link]([Link]); inorder([Link], out);
}
static void preorder(Node r, List<Integer> out) {
if (r == null) return;
[Link]([Link]); preorder([Link], out); preorder([Link], out);
}
static void postorder(Node r, List<Integer> out) {
if (r == null) return;
postorder([Link], out); postorder([Link], out); [Link]([Link]);
}
Height of Tree
static int height(Node r) {
if (r == null) return 0;
return 1 + [Link](height([Link]), height([Link]));
}
Depth of Tree Nodes (level of each node)
static void depths(Node r, int d, Map<Integer, Integer> out) {
if (r == null) return;
[Link]([Link], d);
depths([Link], d + 1, out);
depths([Link], d + 1, out);
}
Level Order of Tree (BFS)
static List<Integer> levelOrder(Node root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Queue<Node> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
Node node = [Link]();
[Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
return res;
}
Zig-Zag Level Order
static List<List<Integer>> zigzagLevelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<Node> q = new LinkedList<>();
[Link](root);
boolean ltr = true;
while (![Link]()) {
int sz = [Link]();
LinkedList<Integer> level = new LinkedList<>();
for (int i = 0; i < sz; i++) {
Node node = [Link]();
if (ltr) [Link]([Link]); else [Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](level);
ltr = !ltr;
}
return res;
}
Left View / Right View of Tree
static List<Integer> rightView(Node root) {
List<Integer> res = new ArrayList<>();
rightViewHelper(root, 0, res);
return res;
}
static void rightViewHelper(Node node, int level, List<Integer> res) {
if (node == null) return;
if (level == [Link]()) [Link]([Link]);
rightViewHelper([Link], level + 1, res);
rightViewHelper([Link], level + 1, res);
}
// For Left View: swap the recursion order above (left before right).
Full Binary Tree check (every node has 0 or 2 children)
static boolean isFull(Node r) {
if (r == null) return true;
if ([Link] == null && [Link] == null) return true;
if ([Link] != null && [Link] != null) return isFull([Link]) && isFull([Link]);
return false;
}
Complete Binary Tree check
static boolean isComplete(Node root) {
Queue<Node> q = new LinkedList<>();
[Link](root);
boolean seenNull = false;
while (![Link]()) {
Node node = [Link]();
if (node == null) {
seenNull = true;
} else {
if (seenNull) return false;
[Link]([Link]);
[Link]([Link]);
}
}
return true;
}
Bottom-Up Level Order
static List<List<Integer>> bottomUpLevelOrder(Node root) {
LinkedList<List<Integer>> levels = new LinkedList<>();
Queue<Node> q = new LinkedList<>();
if (root != null) [Link](root);
while (![Link]()) {
int sz = [Link]();
List<Integer> vals = new ArrayList<>();
for (int i = 0; i < sz; i++) {
Node node = [Link]();
[Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
[Link](vals); // prepend so final list is bottom-up
}
return levels;
}
Zig-Zag Bottom-Up Level Order
Combine the two patterns above: build normal level order top-down alternating direction, then reverse the final list of
levels.
Tip: Don't memorize these verbatim - trace each one on paper with a small example (array of 5 elements, tree of 4 nodes)
until you can rebuild it from the pattern name alone. That's what actually holds up under exam pressure.