25 DSA Formulas & Tricks

1

Middle Index

Binary Search & Pointers Copy

mid = low + (high - low)2

↳ Avoids integer overflow

Used in :

• Binary Search
• Lower Bound
• Upper Bound
• Search in Rotated Array

2

Number of Subarrays

Arrays & Subarrays Copy

n × (n + 1)2

Example : n = 5 = (5 × 6) / 2 = 15 Subarrays

Used in :

• Subarray Problems
• Count all possible subarrays

⎵
n

3

Number of Pairs

Arrays & Subarrays Copy

n × (n - 1)2

Example : n = 6 = (6 × 5) / 2 = 15 Pairs

Used in :

• Count all possible pairs in array
• Pair Sum Problems

4

Reverse an Array

Binary Search & Pointers Copy

arr[left] ↔ arr[right]

left++, right--

Used in :

• Reverse Array
• Two Pointer Problems
• Palindrome Check

5

Swap Without Temp (XOR)

Bit Manipulation Copy

a = a ^ b;

b = a ^ b;

a = a ^ b;

Used in :

• Swap Two Numbers
• Space Optimization
• Bit Manipulation Problems

a

⇄

b

In-place XOR

6

Palindrome Check (String / Number)

Binary Search & Pointers Copy

s[left] == s[right]

left++, right--

Used in :

• Valid Palindrome
• Palindrome Number
• Palindrome Linked List

level

🪞

121

7

Even or Odd

Math & Strings Copy

n % 2 == 0 → Even

n % 2 != 0 → Odd

Used in :

• Even / Odd Check
• Count Even / Odd

2 Even

3 Odd

8

Power of Two

Bit Manipulation Copy

(n & (n - 1)) == 0

Used in :

• Power of Two Check
• Bit Manipulation

💡2ⁿ

9

Count Set Bits (1's in Binary)

Bit Manipulation Copy

while (n > 0) {
    n &= (n - 1);
    count++;
}

Used in :

• Number of 1 Bits
• Hamming Distance
• Bit Manipulation

10101

Hamming wt

10

Toggle Case (Character)

Bit Manipulation Copy

c ^ 32

(A-Z ↔ a-z)

(a-z ↔ A-Z)

Used in :

• Toggle Case in String
• Encryption Problems

A

⇄

a

11

Vowel Check

Math & Strings Copy

aeiouAEIOU

Check if character exists in above set

Used in :

• Count Vowels
• Remove Vowels
• String Problems

aeiou

12

Prefix Sum

Arrays & Subarrays Copy

prefix[0] = arr[0]
for i = 1 to n-1:
    prefix[i] = prefix[i-1] + arr[i]

📌 Range Sum (L to R) = prefix[R] - prefix[L - 1]

Used in :

• Range Sum Queries
• Subarray Sum Problems
• Count of Subarrays
• Hashing Optimization

13

Sliding Window Update

Arrays & Subarrays Copy

windowSum = windowSum - arr[left] + arr[right]
left++, right++

📌 Fixed size window updates in O(1)

Used in :

• Max Sum Subarray (K size)
• Longest Substring
• Anagram Problems
• Minimum Window Substring

arr[L..R]

14

Two Pointer Technique

Binary Search & Pointers Copy

while (left < right)
{
    // process
    left++, right--
}

Used in :

• Pair Sum Problems
• Remove Duplicates
• Palindrome Problems
• 3-Sum / 4-Sum

⮞ left

right ⮜

15

Linked List Reverse

Linked List Copy

prev = null; curr = head;
while (curr != null) {
    next = curr.next
    curr.next = prev
    prev = curr
    curr = next
}
head = prev;

Used in :

• Reverse Linked List
• Palindrome Linked List
• Reorder List
• Flatten Linked List

prev⭠curr⭢next

16

GCD & LCM

Math & Strings Copy

GCD (a, b) = GCD (b, a % b)

LCM (a, b) = (a × b)GCD (a, b)

Used in :

• Math Problems
• Fraction Simplification
• Array Pair GCD
• LCM of Array Elements

🧮

GCD × LCM
= a × b

17

Detect Cycle (Linked List)

Linked List Copy

slow = head;
fast = head;
while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
}
return false;

Used in :

• Linked List Cycle
• Start of Loop in Linked List
• Happy Number
• Circular Array Loop
• Network Connection Problems

18

Merge Two Sorted Arrays

Binary Search & Pointers Copy

while (i < n1 && j < n2)
{
    if (a[i] <= b[j]) res[k++] = a[i++];
    else res[k++] = b[j++];
}

Copy remaining elements

Used in :

• Merge Intervals
• Merge k Sorted Lists
• Count Inversions
• External Sorting
• Median of Two Sorted Arrays

a [•••]

b [•••]

⇣

res [••••••]

19

Binary Search (Iterative)

Binary Search & Pointers Copy

while (low <= high) {
    mid = low + (high - low)/2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
}
return -1;

Used in :

• Search in Sorted Array
• Find Peak Element
• Search Insert Position
• Floor / Ceil in Sorted Array
• Allocate Minimum Pages

🎯 target

LMH

20

Bit Count (Set Bits)

Bit Manipulation Copy

count = 0;
while (n > 0) {
    n = n & (n - 1); // remove rightmost set bit
    count++;
}
// count = number of set bits

Used in :

• Count Set Bits
• Power of Two Check
• Submask Enumeration
• Bit DP Problems
• XOR Based Problems

n & (n - 1)

10100 ↓ 10000

21

Modular Arithmetic

Math & Strings Copy

(a + b) % M = ((a % M) + (b % M)) % M

(a - b) % M = ((a % M) - (b % M) + M) % M

(a * b) % M = ((a % M) * (b % M)) % M

(a ^ b) % M = fast exponentiation

Common M = 1,000,000,007

Used in :

• Large Number Problems
• Combinatorics
• Hashing
• Dynamic Programming
• Competitive Programming

%

10⁹+7

22

Kadane's Algorithm

Arrays & Subarrays Copy

current = max (arr[i], current + arr[i]);

maxSoFar = max (maxSoFar, current);

→ Find Maximum Subarray Sum

→ If all numbers are negative, return the largest element

Used in :

• Maximum Subarray
• Maximum Sum Contiguous Subarray
• Stock Buy Sell (Variation)
• Circular Subarray Sum

23

Longest Substring Without Repeating Characters

Arrays & Subarrays Copy

Use HashMap / Set + Sliding Window

while (right < n) {
    if (s[right] not in map) {
        map[s[right]] = right;
        maxLen = max (maxLen, right - left + 1);
        right++;
    } else {
        left = map[s[right]] + 1;
        map[s[right]] = right;
        right++;
    }
}

abcad

▲ window ▲

Used in :

• Longest Substring Without Repeating Characters
• Longest Nice Substring
• Longest Substring After Replacement
• Minimum Window Substring

🔍unique window

24

Common Complexities

Time Complexity Cheat Sheet

Complexity & Constants Copy

• Access→O(1)

• Search (Unsorted)→O(n)

• Search (Sorted)→O(log n)

• Insertion (End)→O(1)

• Insertion (Any)→O(n)

• Deletion (Any)→O(n)

• Sorting→O(n log n)

• Nested Loop→O(n²)

• All Subsets→O(2ⁿ)

Used in :

• Analyze Time Complexity
• Choose Optimal Approach
• Compare Algorithms
• Optimize Code
• Interview Discussions

</>

25

Important Constants

Useful Values

Complexity & Constants Copy

• MOD Value=1,000,000,007 (10⁹ + 7)

• MOD Value=998,244,353

• ASCII 'A'=65 , 'a' = 97

• Bits in Integer=32

• Max Int (Java)=2³¹ - 1

• Min Int (Java)=-2³¹

• PI Value=3.1415926535

Used in :

• Modular Arithmetic Problems
• Competitive Programming
• Hashing
• Geometry Problems
• Bit Manipulation
• General Calculations

💡

MOD • PI • INT