Crack Your

// ── What does it mean? ──────────────────────────────────────────
// Input: 123  →  Output: 321
// We extract digits one by one from the END using % and build the reversed number.

// APPROACH 1: Loop using % and /  (Standard – Best for interviews)
public static int reverseNumber(int n) {
    int reversed = 0;           // will hold the final reversed number
    while (n != 0) {            // loop until all digits are processed
        int digit = n % 10;     // % gives the LAST digit   e.g. 123%10 = 3
        reversed = reversed * 10 + digit; // shift reversed left, add digit
        n = n / 10;             // remove last digit         e.g. 123/10 = 12
    }
    return reversed;
}
// DRY RUN for n = 123:
// Iteration 1: digit=3, reversed=0*10+3=3,    n=12
// Iteration 2: digit=2, reversed=3*10+2=32,   n=1
// Iteration 3: digit=1, reversed=32*10+1=321, n=0  → loop ends
// Result: 321 ✅

// APPROACH 2: Using String + StringBuilder  (Easiest – 1 line)
public static int reverseV2(int n) {
    String s = String.valueOf(Math.abs(n));           // 123 → "123"
    String rev = new StringBuilder(s).reverse().toString(); // "123" → "321"
    return Integer.parseInt(rev);                     // "321" → 321
}
// Note: Math.abs handles negative numbers

// Output:
// reverseNumber(123)  → 321
// reverseNumber(1200) → 21   (leading zeros dropped)
// reverseNumber(9)    → 9

// Count how many digits are in a number.  1234 → 4 digits

// APPROACH 1: Loop dividing by 10 (Best for interviews)
public static int countDigits(int n) {
    n = Math.abs(n);            // handle negative input
    if (n == 0) return 1;       // special case: 0 has exactly 1 digit
    int count = 0;
    while (n != 0) {
        count++;                // count this digit
        n = n / 10;             // chop off the last digit
    }
    return count;
}
// DRY RUN for n = 4536:
// n=4536 count=1, n=453 count=2, n=45 count=3, n=4 count=4, n=0 → stop
// Result: 4 ✅

// APPROACH 2: String length  (Simplest, 1 line)
public static int countDigitsStr(int n) {
    return String.valueOf(Math.abs(n)).length(); // convert to string, get length
}

// APPROACH 3: Math.log10  (Mathematical trick)
// log10(1000) = 3,  so digits = floor(log10(n)) + 1
public static int countDigitsLog(int n) {
    if (n == 0) return 1;
    return (int)(Math.log10(Math.abs(n))) + 1;
}

// Output:
// countDigits(4536) → 4    countDigits(7) → 1    countDigits(1000) → 4

// Add all digits together.  253 → 2+5+3 = 10

// APPROACH 1: Loop with % (Standard)
public static int sumDigits(int n) {
    n = Math.abs(n);            // handle negatives
    int sum = 0;
    while (n != 0) {
        sum += n % 10;          // add last digit to sum
        n /= 10;                // remove last digit
    }
    return sum;
}
// DRY RUN for n = 253:
// n=253: sum=0+3=3,  n=25
// n=25:  sum=3+5=8,  n=2
// n=2:   sum=8+2=10, n=0  → stop
// Result: 10 ✅

// APPROACH 2: Using chars (String-based)
public static int sumDigitsStr(int n) {
    int sum = 0;
    for (char c : String.valueOf(Math.abs(n)).toCharArray()) {
        sum += (c - '0');   // trick: '5' - '0' = 5  (ASCII subtraction)
    }
    return sum;
}

// Output:
// sumDigits(253) → 10    sumDigits(999) → 27    sumDigits(0) → 0

// A number is palindrome if it reads the same forwards and backwards.
// 121 → palindrome ✅    123 → not ❌

// APPROACH 1: Reverse and compare  (Standard)
public static boolean isNumPalindrome(int n) {
    if (n < 0) return false;    // negative numbers are never palindrome
    int original = n;           // save original to compare later
    int reversed = 0;
    while (n != 0) {
        reversed = reversed * 10 + n % 10; // build reversed number digit by digit
        n /= 10;
    }
    return original == reversed; // same? → palindrome
}
// DRY RUN for n = 121:
// n=121: rev=1, n=12
// n=12:  rev=12, n=1
// n=1:   rev=121, n=0
// original(121) == reversed(121) → true ✅

// APPROACH 2: String comparison  (Easiest)
public static boolean isNumPalindromeStr(int n) {
    String s = String.valueOf(Math.abs(n));
    return s.equals(new StringBuilder(s).reverse().toString());
}

// Output:
// isNumPalindrome(121)  → true    isNumPalindrome(1221) → true
// isNumPalindrome(123)  → false   isNumPalindrome(-121) → false

// Armstrong Number: sum of each digit raised to power of (total digits) = original
// Example: 153 → 1³+5³+3³ = 1+125+27 = 153 ✅
// Example: 9474 → 9⁴+4⁴+7⁴+4⁴ = 6561+256+2401+256 = 9474 ✅

public static boolean isArmstrong(int n) {
    int original = n;
    int digits = String.valueOf(n).length();  // how many digits does n have?
    int sum = 0;
    while (n != 0) {
        int d = n % 10;                        // extract last digit
        sum += (int) Math.pow(d, digits);      // add digit^totalDigits
        n /= 10;                               // remove last digit
    }
    return sum == original;                    // does sum equal the original?
}
// DRY RUN for n = 153  (3 digits):
// d=3: sum=0+27=27,   n=15
// d=5: sum=27+125=152, n=1
// d=1: sum=152+1=153,  n=0
// 153 == 153 → true ✅

// Output:
// isArmstrong(153)  → true    isArmstrong(370)  → true
// isArmstrong(9474) → true    isArmstrong(100)  → false

// Prime: divisible ONLY by 1 and itself.  7 is prime, 6 is not.
// Key trick: only check divisors up to √n — saves time!

// APPROACH 1: Optimized √n check (Best for interviews)
public static boolean isPrime(int n) {
    if (n <= 1) return false;      // 0 and 1 are NOT prime
    if (n == 2) return true;       // 2 is the only even prime
    if (n % 2 == 0) return false;  // all even numbers > 2 are not prime
    for (int i = 3; i * i <= n; i += 2) { // check odd numbers up to √n only
        if (n % i == 0) return false;
    }
    return true;
}
// WHY i*i <= n?
// Divisors come in pairs: for 36 → (2,18)(3,12)(4,9)(6,6)
// After √36=6, divisors just repeat in reverse. No need to go further!

// DRY RUN for n = 17:
// 17%2 ≠ 0 → continue
// i=3: 3*3=9 ≤ 17, 17%3 ≠ 0
// i=5: 5*5=25 > 17 → loop ends
// return true ✅

// APPROACH 2: Brute force  (Simpler to understand)
public static boolean isPrimeSimple(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {  // check every number from 2 to n-1
        if (n % i == 0) return false;
    }
    return true;
}

// Output:
// isPrime(2)  → true    isPrime(7)  → true    isPrime(17) → true
// isPrime(4)  → false   isPrime(1)  → false   isPrime(9)  → false

// APPROACH 1: Use isPrime helper for each number
public static void printPrimes(int n) {
    for (int i = 2; i <= n; i++) {   // start from 2 (smallest prime)
        if (isPrime(i)) System.out.print(i + " ");
    }
}

// APPROACH 2: Sieve of Eratosthenes (Most Efficient — impress interviewers!)
// Idea: cross out all multiples of each prime starting from 2
public static void sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);         // assume all are prime
    isPrime[0] = isPrime[1] = false;    // 0 and 1 are not prime

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {               // if i is still marked prime
            for (int j = i * i; j <= n; j += i) { // mark multiples of i as NOT prime
                isPrime[j] = false;     // starting from i*i (smaller already marked)
            }
        }
    }
    for (int i = 2; i <= n; i++)
        if (isPrime[i]) System.out.print(i + " ");
}
// HOW SIEVE WORKS for n=10:
// Initial: all true except index 0,1
// i=2: mark 4,6,8,10 as false
// i=3: mark 9 as false  (3*3=9)
// Result: 2 3 5 7 ✅

// Output: sieve(20) → 2 3 5 7 11 13 17 19

// GCD = Greatest Common Divisor = largest number that divides BOTH a and b
// GCD(12, 8) = 4  because 4 divides both 12 and 8

// APPROACH 1: Euclidean Algorithm – iterative (Best, O(log n))
// Formula: GCD(a,b) = GCD(b, a%b) until b = 0
public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;   // new b = remainder of a÷b
        a = temp;    // new a = old b
    }
    return a;        // when b=0, a holds the GCD
}
// DRY RUN for gcd(48, 18):
// a=48, b=18 → b=48%18=12, a=18
// a=18, b=12 → b=18%12=6,  a=12
// a=12, b=6  → b=12%6=0,   a=6
// b=0 → return 6 ✅

// APPROACH 2: Recursive
public static int gcdRec(int a, int b) {
    return b == 0 ? a : gcdRec(b, a % b);
}

// BONUS — LCM using GCD:
// LCM(a,b) = (a * b) / GCD(a,b)
public static int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;  // divide first to prevent overflow
}

// Output:
// gcd(48, 18)  → 6      gcd(100, 75) → 25
// lcm(4, 6)    → 12     lcm(3, 5)    → 15

// Factorial: n! = n × (n-1) × (n-2) × ... × 1
// 5! = 5×4×3×2×1 = 120    0! = 1 (by definition)

// APPROACH 1: Iterative Loop (Best for interviews)
public static long factorial(int n) {
    if (n < 0) return -1;        // undefined for negatives
    long result = 1;             // use long — factorials grow very fast!
    for (int i = 2; i <= n; i++) {
        result *= i;             // multiply result by each number
    }
    return result;
}
// DRY RUN for n = 5:
// i=2: result=1×2=2
// i=3: result=2×3=6
// i=4: result=6×4=24
// i=5: result=24×5=120 ✅

// APPROACH 2: Recursive (Classic — must know!)
public static long factRec(int n) {
    if (n == 0 || n == 1) return 1;   // base case
    return n * factRec(n - 1);        // n × factorial of (n-1)
}
// CALL STACK for n=4:
// factRec(4) = 4 × factRec(3)
//              3 × factRec(2)
//              2 × factRec(1) = 1
// returns: 2×1=2 → 3×2=6 → 4×6=24 ✅

// Output:
// factorial(5) → 120    factorial(0) → 1    factorial(10) → 3628800

// Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21 ...
// Each number = sum of the previous two numbers

// APPROACH 1: Iterative (Most Efficient — O(n) time, O(1) space)
public static void printFibonacci(int n) {
    int a = 0, b = 1;
    System.out.print(a + " " + b + " ");  // print first two terms
    for (int i = 2; i < n; i++) {
        int c = a + b;           // next = previous two added together
        System.out.print(c + " ");
        a = b;                   // slide the window: a moves forward
        b = c;                   // b moves forward
    }
}
// DRY RUN for n=7:
// Print 0 1
// i=2: c=1, a=1,b=1 → print 1
// i=3: c=2, a=1,b=2 → print 2
// i=4: c=3, a=2,b=3 → print 3
// i=5: c=5, a=3,b=5 → print 5
// i=6: c=8, a=5,b=8 → print 8
// Output: 0 1 1 2 3 5 8 ✅

// APPROACH 2: Return Nth term
public static int nthFib(int n) {
    if (n <= 1) return n;       // fib(0)=0, fib(1)=1
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) { int c = a+b; a=b; b=c; }
    return b;
}

// Output:
// printFibonacci(8) → 0 1 1 2 3 5 8 13
// nthFib(6)         → 8

// Swap means exchange the values of two variables.
// a=5, b=10  →  a=10, b=5

// APPROACH 1: Using temp variable (SAFE — Always use this in production)
public static void swapWithTemp(int a, int b) {
    System.out.println("Before: a=" + a + ", b=" + b);
    int temp = a;    // Step 1: save a's value in temp  → temp=5
    a = b;           // Step 2: put b's value into a    → a=10
    b = temp;        // Step 3: put temp's value into b → b=5
    System.out.println("After:  a=" + a + ", b=" + b);
}
// DRY RUN for a=5, b=10:
// temp=5 → a=10 → b=5 ✅

// Output: Before: a=5, b=10   After: a=10, b=5

// APPROACH 1: Arithmetic – using + and -
public static void swapNoTemp(int a, int b) {
    System.out.println("Before: a=" + a + ", b=" + b);
    a = a + b;   // a = 5+10 = 15  (a now holds the sum)
    b = a - b;   // b = 15-10 = 5  (subtract original b → get original a)
    a = a - b;   // a = 15-5  = 10 (subtract original a → get original b)
    System.out.println("After:  a=" + a + ", b=" + b);
}
// ⚠️ Risk: overflow if a+b exceeds Integer.MAX_VALUE

// APPROACH 2: XOR Bitwise (No overflow risk — Pro technique!)
public static void swapXOR(int a, int b) {
    a = a ^ b;   // a = a XOR b
    b = a ^ b;   // b = (a XOR b) XOR b = a  (original)
    a = a ^ b;   // a = (a XOR b) XOR a = b  (original)
    System.out.println("After XOR: a=" + a + ", b=" + b);
}
// XOR trick: x ^ x = 0  and  x ^ 0 = x

// Output: Before: a=5, b=10   After: a=10, b=5

// APPROACH 1: if-else chain (Clear and readable)
public static int largest3(int a, int b, int c) {
    if (a >= b && a >= c) return a;  // a is largest
    else if (b >= c)      return b;  // b is largest
    else                  return c;  // c is largest
}

// APPROACH 2: Nested Math.max (Cleanest)
public static int largest3V2(int a, int b, int c) {
    return Math.max(a, Math.max(b, c)); // find max of b&c, then compare with a
}

// APPROACH 3: Ternary operator
public static int largest3V3(int a, int b, int c) {
    int ab = (a > b) ? a : b;          // max of a and b
    return (ab > c) ? ab : c;          // max of ab and c
}

// Output:
// largest3(5, 9, 3)    → 9     largest3(20, 15, 20) → 20
// largest3(-1, -5, -3) → -1

// Even: divisible by 2 (last digit 0,2,4,6,8)
// Odd:  NOT divisible by 2 (last digit 1,3,5,7,9)

// APPROACH 1: Modulo operator (Standard)
public static String evenOdd(int n) {
    return (n % 2 == 0) ? n + " is Even" : n + " is Odd";
}

// APPROACH 2: Bitwise AND (Fastest — used in performance-critical code)
// How it works: even numbers end in 0 in binary, odd end in 1
// n & 1  checks the last bit only
public static String evenOddBit(int n) {
    return ((n & 1) == 0) ? n + " is Even" : n + " is Odd";
}
// Binary examples:
// 4  = 0100  →  0100 & 0001 = 0  → Even ✅
// 7  = 0111  →  0111 & 0001 = 1  → Odd  ✅
// 10 = 1010  →  1010 & 0001 = 0  → Even ✅

// Output:
// evenOdd(4) → Even    evenOdd(7) → Odd    evenOdd(-6) → Even

// Natural numbers: 1, 2, 3, 4 ... N

// APPROACH 1: Formula — O(1) INSTANT! (Best)
// Sum = N × (N+1) / 2  ← Gauss formula
public static long sumN(int n) {
    return (long) n * (n + 1) / 2;  // cast to long to prevent overflow
}
// Example: n=100 → 100×101/2 = 5050

// APPROACH 2: For loop — O(n)
public static long sumNLoop(int n) {
    long sum = 0;
    for (int i = 1; i <= n; i++) sum += i;
    return sum;
}
// DRY RUN for n=5:
// i=1:sum=1, i=2:sum=3, i=3:sum=6, i=4:sum=10, i=5:sum=15 ✅

// APPROACH 3: Recursive
public static long sumNRec(int n) {
    return (n == 0) ? 0 : n + sumNRec(n - 1);
}

// Output:
// sumN(100) → 5050    sumN(10) → 55    sumN(5) → 15

// APPROACH 1: For loop (Without inbuilt — best for interviews)
public static String reverseStr(String s) {
    String result = "";
    for (int i = s.length() - 1; i >= 0; i--) {
        result += s.charAt(i);  // add each char from end to start
    }
    return result;
}

// APPROACH 2: Two Pointer on char array (Efficient, O(n))
public static String reverseV2(String s) {
    char[] arr = s.toCharArray();   // "Hello" → ['H','e','l','l','o']
    int left = 0, right = arr.length - 1;
    while (left < right) {
        char temp = arr[left];      // swap left and right chars
        arr[left] = arr[right];
        arr[right] = temp;
        left++;  right--;           // move pointers inward
    }
    return new String(arr);
}
// DRY RUN for "Java":
// arr=[J,a,v,a]
// left=0,right=3 → swap J,a → [a,a,v,J]
// left=1,right=2 → swap a,v → [a,v,a,J]
// Result: "avaJ" ✅

// APPROACH 3: StringBuilder.reverse() (Inbuilt — simplest)
public static String reverseV3(String s) {
    return new StringBuilder(s).reverse().toString();
}

// Output:
// reverseStr("Hello") → "olleH"    reverseV3("Java") → "avaJ"

// Palindrome: reads same forwards and backwards.  "racecar" ✅  "hello" ❌

// APPROACH 1: Two Pointer (Best — O(n), no extra space)
public static boolean isPalindromeStr(String s) {
    s = s.toLowerCase();         // make comparison case-insensitive
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false; // mismatch!
        left++;  right--;
    }
    return true;
}
// DRY RUN for "racecar":
// l=0,r=6: r==r ✅   l=1,r=5: a==a ✅   l=2,r=4: c==c ✅
// l=3=r=3: pointers meet → stop → return true ✅

// APPROACH 2: Reverse and compare (Simple)
public static boolean isPalindromeV2(String s) {
    String low = s.toLowerCase();
    return low.equals(new StringBuilder(low).reverse().toString());
}

// Output:
// isPalindromeStr("racecar") → true     isPalindromeStr("Madam") → true
// isPalindromeStr("hello")   → false

// APPROACH 1: split() with \\s+ (Handles multiple spaces, tabs)
public static int countWords(String s) {
    s = s.trim();                  // remove leading/trailing spaces
    if (s.isEmpty()) return 0;
    return s.split("\\s+").length; // \\s+ = one or more whitespace chars
}

// APPROACH 2: Manual loop (Without inbuilt)
public static int countWordsManual(String s) {
    int count = 0;
    boolean inWord = false;
    for (char c : s.toCharArray()) {
        if (c != ' ' && !inWord) { // entering a new word
            count++;
            inWord = true;
        } else if (c == ' ') {
            inWord = false;         // leaving a word
        }
    }
    return count;
}
// DRY RUN for "Hello World Java":
// H→inWord=true,count=1  space→inWord=false
// W→inWord=true,count=2  space→inWord=false
// J→inWord=true,count=3  → end
// Result: 3 ✅

// Output:
// countWords("Hello World Java") → 3    countWords("  Hi   there  ") → 2

// Vowels: a e i o u    Consonants: all other alphabets

public static void countVC(String s) {
    s = s.toLowerCase();           // normalize: treat A and a the same
    int vowels = 0, consonants = 0;
    for (char c : s.toCharArray()) {
        if (c >= 'a' && c <= 'z') {          // only process alphabet chars
            if ("aeiou".indexOf(c) != -1) {   // is it a vowel?
                vowels++;
            } else {
                consonants++;                  // it's a consonant
            }
        }
        // spaces, digits, symbols are simply ignored
    }
    System.out.println("Vowels: " + vowels + ", Consonants: " + consonants);
}
// DRY RUN for "Hello":
// h→consonant(1)  e→vowel(1)  l→consonant(2)  l→consonant(3)  o→vowel(2)
// Vowels=2, Consonants=3 ✅

// Output:
// countVC("Java")    → Vowels: 2, Consonants: 2
// countVC("Hello!")  → Vowels: 2, Consonants: 3

// APPROACH 1: replaceAll with regex (Easiest — 1 line)
public static String removeSpaces(String s) {
    return s.replaceAll("\\s", ""); // \\s matches space, tab, newline — replaces with ""
}

// APPROACH 2: Loop (Without inbuilt — for interview)
public static String removeSpacesManual(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (c != ' ') sb.append(c);  // only keep non-space characters
    }
    return sb.toString();
}

// APPROACH 3: Stream (Java 8+)
public static String removeSpacesStream(String s) {
    return s.chars()
            .filter(c -> c != ' ')
            .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
            .toString();
}

// Output:
// removeSpaces("Hello World") → "HelloWorld"
// removeSpaces("J a v a")     → "Java"

// Input:  "Hello World Java"
// Output: "olleH dlroW avaJ"   — each word reversed, order stays same

public static String reverseEachWord(String s) {
    String[] words = s.split(" ");         // split into array of words
    StringBuilder result = new StringBuilder();
    for (String word : words) {
        result.append(new StringBuilder(word).reverse()); // reverse each word
        result.append(" ");                 // add space separator
    }
    return result.toString().trim();        // remove trailing space
}
// ITERATION for "Hi Java":
// word="Hi"   → "iH"
// word="Java" → "avaJ"
// Result: "iH avaJ" ✅

// Output:
// reverseEachWord("Hello World") → "olleH dlroW"
// reverseEachWord("Java is fun") → "avaJ si nuf"

// Input:  "Hello World Java"
// Output: "Java World Hello"   — word ORDER reversed, each word stays same

// APPROACH 1: Split → reverse array → join
public static String reverseWordOrder(String s) {
    String[] words = s.trim().split("\\s+"); // split on any whitespace
    int left = 0, right = words.length - 1;
    while (left < right) {
        String tmp = words[left];   // swap words at left and right positions
        words[left] = words[right];
        words[right] = tmp;
        left++;  right--;
    }
    return String.join(" ", words); // join array back into sentence
}
// DRY RUN for "Java is great":
// words = ["Java","is","great"]
// swap index 0 and 2: ["great","is","Java"]
// Result: "great is Java" ✅

// APPROACH 2: Collections.reverse (One-liner style)
public static String reverseWordOrderV2(String s) {
    List list = new ArrayList<>(Arrays.asList(s.trim().split("\\s+")));
    Collections.reverse(list);
    return String.join(" ", list);
}

// Output:
// reverseWordOrder("Hello World Java") → "Java World Hello"

// APPROACH 1: Manual conversion (Shows how parseInt works internally)
public static int strToInt(String s) {
    int result = 0;
    boolean negative = false;
    int start = 0;
    if (s.charAt(0) == '-') { negative = true; start = 1; } // handle sign
    for (int i = start; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c < '0' || c > '9') throw new IllegalArgumentException("Invalid: " + c);
        int digit = c - '0';              // ASCII trick: '5'-'0' = 5
        result = result * 10 + digit;     // build number digit by digit
    }
    return negative ? -result : result;
}
// DRY RUN for "123":
// c='1': digit=1, result=1
// c='2': digit=2, result=12
// c='3': digit=3, result=123 ✅

// APPROACH 2: Integer.parseInt (Standard)
public static int strToIntBuiltin(String s) {
    return Integer.parseInt(s);  // throws NumberFormatException if invalid
}

// Output:
// strToInt("123") → 123    strToInt("-45") → -45

// APPROACH 1: Loop (Without inbuilt)
public static boolean isAllDigits(String s) {
    if (s == null || s.isEmpty()) return false;
    for (char c : s.toCharArray()) {
        if (c < '0' || c > '9') return false; // found a non-digit
    }
    return true;
}

// APPROACH 2: matches() with regex (Simplest)
public static boolean isAllDigitsRegex(String s) {
    return s != null && s.matches("\\d+"); // \\d = digit, + = one or more
}

// APPROACH 3: Character.isDigit() with stream (Java 8)
public static boolean isAllDigitsStream(String s) {
    return s != null && !s.isEmpty() && s.chars().allMatch(Character::isDigit);
}

// Output:
// isAllDigits("12345") → true    isAllDigits("123a5") → false

// APPROACH 1: LinkedHashMap (Best — handles all chars, preserves order)
public static void charFrequency(String s) {
    Map map = new LinkedHashMap<>();
    for (char c : s.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1); // if key exists add 1, else put 1
    }
    for (Map.Entry e : map.entrySet()) {
        System.out.println("'" + e.getKey() + "' → " + e.getValue());
    }
}

// APPROACH 2: int array (Only lowercase a-z — faster, less memory)
public static void charFreqArray(String s) {
    int[] freq = new int[26];  // index 0=a, 1=b, ..., 25=z
    for (char c : s.toLowerCase().toCharArray()) {
        if (c >= 'a' && c <= 'z') freq[c - 'a']++; // map 'a'→0, 'b'→1 etc.
    }
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) System.out.println((char)('a' + i) + " → " + freq[i]);
    }
}
// DRY RUN for "aabb":
// 'a':map={a:1}, 'a':map={a:2}, 'b':map={a:2,b:1}, 'b':map={a:2,b:2}
// Output: a→2, b→2 ✅

// Output for "programming": p→1, r→2, o→1, g→2, a→1, m→2, i→1, n→1

// First character that appears ONLY once.   "aabbcd" → 'c'

// APPROACH 1: LinkedHashMap — two passes (Best)
public static char firstNonRepeating(String s) {
    Map map = new LinkedHashMap<>(); // preserves insertion order
    for (char c : s.toCharArray())
        map.put(c, map.getOrDefault(c, 0) + 1); // pass 1: build frequency map
    for (Map.Entry e : map.entrySet())
        if (e.getValue() == 1) return e.getKey(); // pass 2: first with count=1
    return '_'; // no non-repeating char found
}

// APPROACH 2: int array — two passes (Faster for a-z)
public static char firstNonRepArray(String s) {
    int[] freq = new int[256]; // all ASCII characters
    for (char c : s.toCharArray()) freq[c]++;      // pass 1: count
    for (char c : s.toCharArray())                 // pass 2: find first with 1
        if (freq[c] == 1) return c;
    return '_';
}
// DRY RUN for "aabbcd":
// map: a→2, b→2, c→1, d→1
// first entry with value=1 → 'c' ✅

// Output:
// firstNonRepeating("aabbcd")   → c
// firstNonRepeating("leetcode") → l
// firstNonRepeating("aabb")     → _

// Characters that appear MORE THAN ONCE

// APPROACH 1: HashMap — count then filter
public static void findDuplicates(String s) {
    Map map = new LinkedHashMap<>();
    for (char c : s.toLowerCase().toCharArray())
        map.put(c, map.getOrDefault(c, 0) + 1);
    System.out.print("Duplicates: ");
    for (Map.Entry e : map.entrySet())
        if (e.getValue() > 1)
            System.out.print(e.getKey() + "(" + e.getValue() + ") ");
}

// APPROACH 2: Two Sets (seen + duplicates)
public static void findDuplicatesSet(String s) {
    Set seen = new HashSet<>();
    Set dups = new LinkedHashSet<>();
    for (char c : s.toCharArray())
        if (!seen.add(c)) dups.add(c); // add() returns false if already present
    System.out.println("Duplicates: " + dups);
}
// DRY RUN for "programming":
// seen: p,r→ r again! dup={r}  g→ g again! dup={r,g}  m→ m again! dup={r,g,m}

// Output:
// findDuplicates("programming") → r(2) g(2) m(2)

// Anagram: same characters, different arrangement.  "listen" = "silent" ✅

// APPROACH 1: Sort both and compare (Simple, O(n log n))
public static boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false; // lengths must match
    char[] ca = a.toLowerCase().toCharArray();
    char[] cb = b.toLowerCase().toCharArray();
    Arrays.sort(ca);  Arrays.sort(cb);           // sort both
    return Arrays.equals(ca, cb);                // compare sorted arrays
}

// APPROACH 2: Frequency array (Better, O(n) no sorting)
public static boolean isAnagramV2(String a, String b) {
    if (a.length() != b.length()) return false;
    int[] freq = new int[26];
    for (int i = 0; i < a.length(); i++) {
        freq[a.charAt(i) - 'a']++;   // +1 for each char in a
        freq[b.charAt(i) - 'a']--;   // -1 for each char in b
    }
    for (int f : freq) if (f != 0) return false; // any mismatch → not anagram
    return true;
}
// DRY RUN for "listen" vs "silent":
// After sort: "eilnst" == "eilnst" → true ✅

// Output:
// isAnagram("listen","silent")   → true
// isAnagram("Anagram","Nagaram") → true
// isAnagram("hello","world")     → false

// Keep only FIRST occurrence of each character.
// "programming" → "progamin"

// APPROACH 1: LinkedHashSet (Best — preserves order, auto-removes dups)
public static String removeDups(String s) {
    Set seen = new LinkedHashSet<>();
    for (char c : s.toCharArray()) seen.add(c); // Set ignores duplicates automatically
    StringBuilder sb = new StringBuilder();
    for (char c : seen) sb.append(c);
    return sb.toString();
}

// APPROACH 2: Manual boolean array (Without collections)
public static String removeDupsManual(String s) {
    boolean[] seen = new boolean[256]; // one slot per ASCII character
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (!seen[c]) {       // first time seeing this char?
            sb.append(c);     // add it to result
            seen[c] = true;   // mark as seen
        }
    }
    return sb.toString();
}
// DRY RUN for "aabbcc":
// a:new→add  a:seen→skip  b:new→add  b:seen→skip  c:new→add  c:seen→skip
// Result: "abc" ✅

// Output:
// removeDups("programming") → "progamin"    removeDups("aabbcc") → "abc"

// Largest = word with most characters
// "Java is a programming language" → "programming" (11 chars)

// APPROACH 1: Loop — compare lengths
public static String largestWord(String s) {
    String[] words = s.trim().split("\\s+");
    String largest = "";
    for (String word : words) {
        if (word.length() > largest.length()) {
            largest = word;  // update if this word is longer
        }
    }
    return largest;
}
// ITERATION for "Java is a programming language":
// "Java"(4) > ""(0)           → largest="Java"
// "is"(2) < "Java"(4)         → skip
// "a"(1) < "Java"(4)          → skip
// "programming"(11) > "Java"  → largest="programming"
// "language"(8) < "programming" → skip
// Result: "programming" ✅

// APPROACH 2: Stream (Java 8 — elegant)
public static String largestWordStream(String s) {
    return Arrays.stream(s.trim().split("\\s+"))
                 .max(Comparator.comparingInt(String::length))
                 .orElse("");
}

// Output:
// largestWord("Java is programming")   → "programming"
// largestWord("Hi there everyone")     → "everyone"

// APPROACH 1: Loop (Without inbuilt — Best for interview)
public static int findLargest(int[] arr) {
    int max = arr[0];            // assume first element is largest
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i]; // update max if current is bigger
    }
    return max;
}
// DRY RUN for [3, 7, 1, 9, 4]:
// max=3 → arr[1]=7>3 → max=7 → arr[2]=1<7 → arr[3]=9>7 → max=9 → arr[4]=4<9
// Result: 9 ✅

// APPROACH 2: Arrays.stream (Java 8 — 1 line)
public static int findLargestStream(int[] arr) {
    return Arrays.stream(arr).max().getAsInt();
}

// Output: findLargest([3,7,1,9,4]) → 9

// Same logic as largest — just flip the comparison
public static int findSmallest(int[] arr) {
    int min = arr[0];            // assume first element is smallest
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < min) min = arr[i]; // update if current is smaller
    }
    return min;
}
// DRY RUN for [3, 7, 1, 9, 4]:
// min=3 → 7>3 skip → 1<3 min=1 → 9>1 skip → 4>1 skip
// Result: 1 ✅

// APPROACH 2: Stream
public static int findSmallestStream(int[] arr) {
    return Arrays.stream(arr).min().getAsInt();
}

// APPROACH 1: Single pass — track both max and second max
public static int secondLargest(int[] arr) {
    int max = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
    for (int n : arr) {
        if (n > max) {
            second = max;  // old max becomes second
            max = n;       // new max found
        } else if (n > second && n != max) {
            second = n;    // update second if bigger than current second (and not equal to max)
        }
    }
    return second;
}
// DRY RUN for [3, 7, 1, 9, 4]:
// n=3: max=3, second=MIN
// n=7: 7>3 → second=3, max=7
// n=1: 1<7 and 1<3 → skip
// n=9: 9>7 → second=7, max=9
// n=4: 4<9 and 4>7? No. 4>second(7)? No → skip
// Result: 7 ✅

// APPROACH 2: Sort (Simple but O(n log n))
public static int secondLargestSort(int[] arr) {
    int[] sorted = Arrays.copyOf(arr, arr.length);
    Arrays.sort(sorted);  // sort ascending
    return sorted[sorted.length - 2]; // second from end
}
// ⚠️ Won't work for duplicates like [5,5,3] — use APPROACH 1 instead

// Output: secondLargest([3,7,1,9,4]) → 7

// APPROACH 1: Two pointer (In-place, no extra space)
public static void reverseArray(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int temp = arr[left];    // swap arr[left] and arr[right]
        arr[left] = arr[right];
        arr[right] = temp;
        left++;  right--;        // move pointers inward
    }
}
// DRY RUN for [1, 2, 3, 4, 5]:
// l=0,r=4: swap 1,5 → [5,2,3,4,1]
// l=1,r=3: swap 2,4 → [5,4,3,2,1]
// l=2,r=2: pointers meet → stop
// Result: [5,4,3,2,1] ✅

// APPROACH 2: New array (If you need original preserved)
public static int[] reverseArrayNew(int[] arr) {
    int[] result = new int[arr.length];
    for (int i = 0; i < arr.length; i++)
        result[i] = arr[arr.length - 1 - i]; // fill from end of original
    return result;
}

// Sorted (ascending): each element <= next element
// [1,2,3,4,5] ✅   [1,3,2,4] ❌

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) return false; // found a pair out of order
    }
    return true; // all pairs were in order
}
// DRY RUN for [1, 3, 2, 4]:
// i=0: arr[0]=1 <= arr[1]=3 ✅
// i=1: arr[1]=3 > arr[2]=2 ❌ → return false ✅

// Output:
// isSorted([1,2,3,4,5]) → true    isSorted([1,3,2,4]) → false

// Left rotate: first element goes to end
// [1,2,3,4,5] → [2,3,4,5,1]

public static void leftRotateOne(int[] arr) {
    int first = arr[0];                      // save first element
    for (int i = 0; i < arr.length - 1; i++) {
        arr[i] = arr[i + 1];                 // shift each element one step left
    }
    arr[arr.length - 1] = first;             // put saved element at end
}
// DRY RUN for [1,2,3,4,5]:
// first=1
// arr=[2,3,4,5,5] (shifting)
// arr[4]=1 → [2,3,4,5,1] ✅

// [1,2,3,4,5], K=2 → [3,4,5,1,2]

// APPROACH 1: Reversal Algorithm (Most Efficient — O(n), O(1) space)
// Step 1: Reverse first K elements
// Step 2: Reverse remaining elements
// Step 3: Reverse entire array
public static void leftRotateK(int[] arr, int k) {
    int n = arr.length;
    k = k % n;              // handle k > n  (e.g. k=7 on size 5 = k=2)
    reverse(arr, 0, k - 1); // reverse [0..k-1]
    reverse(arr, k, n - 1); // reverse [k..n-1]
    reverse(arr, 0, n - 1); // reverse entire array
}
public static void reverse(int[] arr, int l, int r) {
    while (l < r) { int t=arr[l]; arr[l]=arr[r]; arr[r]=t; l++; r--; }
}
// DRY RUN for [1,2,3,4,5], K=2:
// Reverse [0..1]: [2,1,3,4,5]
// Reverse [2..4]: [2,1,5,4,3]
// Reverse all:    [3,4,5,1,2] ✅

// APPROACH 2: Using temp array (Simpler to understand)
public static void leftRotateKSimple(int[] arr, int k) {
    int n = arr.length;  k = k % n;
    int[] temp = Arrays.copyOfRange(arr, 0, k); // save first k elements
    for (int i = 0; i < n - k; i++) arr[i] = arr[i + k]; // shift left
    for (int i = 0; i < k; i++) arr[n - k + i] = temp[i]; // fill end
}

// [1,2,3,4,5], K=2 → [4,5,1,2,3]
// Right rotate K = Left rotate (n-K)

public static void rightRotateK(int[] arr, int k) {
    int n = arr.length;
    k = k % n;              // normalize k
    // Right rotation K = Left rotation (n-K)
    reverse(arr, 0, n - k - 1); // reverse first (n-k) elements
    reverse(arr, n - k, n - 1); // reverse last k elements
    reverse(arr, 0, n - 1);     // reverse entire array
}
// DRY RUN for [1,2,3,4,5], K=2 (n=5):
// Reverse [0..2]: [3,2,1,4,5]
// Reverse [3..4]: [3,2,1,5,4]
// Reverse all:    [4,5,1,2,3] ✅

// Since array is SORTED, duplicates are always adjacent.
// [1,1,2,2,3,4,4] → [1,2,3,4] — return count of unique elements

// Two Pointer technique (O(n), O(1) space — Best)
public static int removeDuplicatesSorted(int[] arr) {
    if (arr.length == 0) return 0;
    int j = 0; // j = position to place next unique element
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != arr[j]) { // found a new unique element
            j++;                 // advance write pointer
            arr[j] = arr[i];    // write it to correct position
        }
    }
    return j + 1; // number of unique elements
}
// DRY RUN for [1,1,2,2,3]:
// j=0 (arr[j]=1)
// i=1: arr[1]=1 == arr[j]=1 → skip
// i=2: arr[2]=2 != arr[j]=1 → j=1, arr[1]=2 → [1,2,2,2,3]
// i=3: arr[3]=2 == arr[j]=2 → skip
// i=4: arr[4]=3 != arr[j]=2 → j=2, arr[2]=3 → [1,2,3,2,3]
// return 3 ✅  (first 3 elements: [1,2,3])

// Find all elements that appear more than once
// [1,2,3,2,4,3] → duplicates: 2, 3

// APPROACH 1: HashSet — add and detect duplicates
public static void findDuplicatesArr(int[] arr) {
    Set seen = new HashSet<>();
    Set dups = new LinkedHashSet<>();
    for (int n : arr) {
        if (!seen.add(n)) dups.add(n); // add() returns false = already existed
    }
    System.out.println("Duplicates: " + dups);
}

// APPROACH 2: HashMap frequency count
public static void findDuplicatesMap(int[] arr) {
    Map map = new LinkedHashMap<>();
    for (int n : arr) map.put(n, map.getOrDefault(n, 0) + 1);
    for (Map.Entry e : map.entrySet())
        if (e.getValue() > 1) System.out.print(e.getKey() + " ");
}
// DRY RUN for [1,2,3,2,4,3]:
// seen: 1,2,3 → 2 already! dup={2} → 4 → 3 already! dup={2,3}
// Output: 2 3 ✅

// Print how many times each element appears
// [1,2,2,3,3,3] → 1→1, 2→2, 3→3

public static void countFrequency(int[] arr) {
    Map map = new LinkedHashMap<>();
    for (int n : arr)
        map.put(n, map.getOrDefault(n, 0) + 1); // count each element
    for (Map.Entry e : map.entrySet())
        System.out.println(e.getKey() + " → " + e.getValue());
}
// DRY RUN for [1,2,2,3]:
// 1→1, 2→1 then 2→2, 3→1
// Output: 1→1, 2→2, 3→1 ✅

// [2, 3, 2, 4, 3] → answer is 4  (only 4 appears once)

// APPROACH 1: XOR trick (Most elegant — O(n), O(1) space!)
// Key property: x ^ x = 0  and  x ^ 0 = x
// So XOR of all elements — pairs cancel out, leaving the single element
public static int findSingle(int[] arr) {
    int result = 0;
    for (int n : arr) result ^= n;  // XOR all elements
    return result;
}
// DRY RUN for [2,3,2,4,3]:
// result = 0^2=2 → 2^3=1 → 1^2=3 → 3^4=7 → 7^3=4
// Result: 4 ✅ (pairs cancel: 2^2=0, 3^3=0)

// APPROACH 2: HashMap (Easier to understand)
public static int findSingleMap(int[] arr) {
    Map map = new HashMap<>();
    for (int n : arr) map.put(n, map.getOrDefault(n,0)+1);
    for (Map.Entry e : map.entrySet())
        if (e.getValue() == 1) return e.getKey();
    return -1;
}

// Output: findSingle([2,3,2,4,3]) → 4

// Array has n-1 elements from 1 to n, one number missing.
// [1,2,4,5] from 1-5 → missing is 3

// APPROACH 1: Sum formula (Best — O(n), O(1))
// Expected sum of 1 to N = N*(N+1)/2
// Missing = Expected sum − Actual sum
public static int findMissing(int[] arr, int n) {
    int expected = n * (n + 1) / 2;  // what the sum SHOULD be
    int actual = 0;
    for (int x : arr) actual += x;   // what the sum actually is
    return expected - actual;         // difference = missing number
}
// DRY RUN for [1,2,4,5], n=5:
// expected = 5*6/2 = 15
// actual   = 1+2+4+5 = 12
// missing  = 15-12 = 3 ✅

// APPROACH 2: XOR (Handles large numbers without overflow)
public static int findMissingXOR(int[] arr, int n) {
    int xor = 0;
    for (int i = 1; i <= n; i++) xor ^= i;   // XOR all 1 to N
    for (int x : arr) xor ^= x;              // XOR with all array elements
    return xor;  // all pairs cancel, leaving the missing number
}

// In binary array, find longest run of consecutive 1s
// [1,1,0,1,1,1] → 3

public static int maxConsecutiveOnes(int[] arr) {
    int maxCount = 0;    // overall maximum
    int count = 0;       // current run of ones
    for (int n : arr) {
        if (n == 1) {
            count++;                       // extend current run
            maxCount = Math.max(maxCount, count); // update max if needed
        } else {
            count = 0;                     // reset run on seeing 0
        }
    }
    return maxCount;
}
// DRY RUN for [1,1,0,1,1,1]:
// n=1:count=1,max=1  n=1:count=2,max=2  n=0:count=0
// n=1:count=1,max=2  n=1:count=2,max=2  n=1:count=3,max=3
// Result: 3 ✅

// Output:
// maxConsecutiveOnes([1,1,0,1,1,1]) → 3
// maxConsecutiveOnes([0,0,1,0])     → 1

// [1,3,5] + [2,4,6] → [1,2,3,4,5,6]
// Both arrays already sorted — merge without sorting again

public static int[] mergeSorted(int[] a, int[] b) {
    int i = 0, j = 0, k = 0;
    int[] result = new int[a.length + b.length];
    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) result[k++] = a[i++]; // pick smaller element
        else               result[k++] = b[j++];
    }
    while (i < a.length) result[k++] = a[i++]; // copy remaining from a
    while (j < b.length) result[k++] = b[j++]; // copy remaining from b
    return result;
}
// DRY RUN for [1,3,5] and [2,4,6]:
// i=0,j=0: 1<2 → result[0]=1, i=1
// i=1,j=0: 3>2 → result[1]=2, j=1
// i=1,j=1: 3<4 → result[2]=3, i=2
// i=2,j=1: 5>4 → result[3]=4, j=2
// i=2,j=2: 5<6 → result[4]=5, i=3 → loop ends
// copy remaining b: result[5]=6
// Result: [1,2,3,4,5,6] ✅

// Elements that exist in BOTH arrays (no duplicates)
// [1,2,3,4] ∩ [3,4,5,6] → [3,4]

public static List intersection(int[] a, int[] b) {
    Set setA = new HashSet<>();
    for (int x : a) setA.add(x);          // put all of a into a set

    Set result = new LinkedHashSet<>();
    for (int x : b) {
        if (setA.contains(x)) result.add(x); // if b's element exists in a → common
    }
    return new ArrayList<>(result);
}
// DRY RUN for [1,2,3,4] and [3,4,5,6]:
// setA = {1,2,3,4}
// b: 3→in setA! 4→in setA! 5→not in setA. 6→not in setA.
// result = {3,4} ✅

// All unique elements from BOTH arrays combined
// [1,2,3] ∪ [3,4,5] → [1,2,3,4,5]

public static List union(int[] a, int[] b) {
    Set set = new LinkedHashSet<>(); // preserves insertion order
    for (int x : a) set.add(x);  // add all of a
    for (int x : b) set.add(x);  // add all of b (duplicates auto-ignored by Set)
    return new ArrayList<>(set);
}
// LinkedHashSet automatically handles:
// 1. Removing duplicates (Set property)
// 2. Preserving insertion order (Linked property)

// Output:
// union([1,2,3],[3,4,5]) → [1,2,3,4,5]

// Find if any two elements sum to a target value
// [2,7,4,3], target=9 → 2+7=9 ✅

// APPROACH 1: HashMap (O(n) — Best)
public static void twoSum(int[] arr, int target) {
    Map map = new HashMap<>(); // stores value → index
    for (int i = 0; i < arr.length; i++) {
        int complement = target - arr[i];  // what number do we need?
        if (map.containsKey(complement)) {
            System.out.println("Pair found: " + complement + " + " + arr[i]);
        }
        map.put(arr[i], i);               // store current element
    }
}
// DRY RUN for [2,7,4,3], target=9:
// i=0: need 9-2=7 → not in map. map={2:0}
// i=1: need 9-7=2 → 2 IS in map! → Print: 2+7=9 ✅

// APPROACH 2: Brute force (O(n²) — Easy to understand)
public static void twoSumBrute(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++)
        for (int j = i+1; j < arr.length; j++)
            if (arr[i] + arr[j] == target)
                System.out.println(arr[i] + " + " + arr[j]);
}

// Majority element: appears more than n/2 times
// [3,3,4,2,3,3,3] → 3  (appears 5 times in array of 7)

// APPROACH 1: Boyer-Moore Voting Algorithm (O(n), O(1) — Pro!)
public static int majorityElement(int[] arr) {
    int candidate = arr[0], votes = 1;
    for (int i = 1; i < arr.length; i++) {
        if (votes == 0) {
            candidate = arr[i]; // reset candidate
            votes = 1;
        } else if (arr[i] == candidate) {
            votes++;             // same element — add vote
        } else {
            votes--;             // different element — cancel vote
        }
    }
    return candidate;  // candidate with remaining votes is majority
}
// DRY RUN for [3,3,4,2,3,3,3]:
// cand=3,v=1 → 3:v=2 → 4:v=1 → 2:v=0 → reset:cand=3,v=1 → 3:v=2 → 3:v=3
// Result: 3 ✅

// APPROACH 2: HashMap (Simpler to understand)
public static int majorityElementMap(int[] arr) {
    Map map = new HashMap<>();
    for (int n : arr) map.put(n, map.getOrDefault(n,0)+1);
    for (Map.Entry e : map.entrySet())
        if (e.getValue() > arr.length/2) return e.getKey();
    return -1;
}

// Find contiguous subarray with largest sum
// [-2,1,-3,4,-1,2,1,-5,4] → 6  (subarray [4,-1,2,1])

// Kadane's Algorithm — O(n), O(1)
public static int maxSubarraySum(int[] arr) {
    int maxSum = arr[0];     // overall max seen so far
    int current = arr[0];    // current running sum
    for (int i = 1; i < arr.length; i++) {
        // either extend existing subarray OR start fresh from arr[i]
        current = Math.max(arr[i], current + arr[i]);
        maxSum = Math.max(maxSum, current); // update global max
    }
    return maxSum;
}
// DRY RUN for [-2,1,-3,4,-1,2,1,-5,4]:
// current=-2, max=-2
// i=1: max(1,-2+1=-1)=1,  max=-2→1=1
// i=2: max(-3,1-3=-2)=-2, max=1
// i=3: max(4,-2+4=2)=4,   max=4
// i=4: max(-1,4-1=3)=3,   max=4
// i=5: max(2,3+2=5)=5,    max=5
// i=6: max(1,5+1=6)=6,    max=6 ✅
// Result: 6

// Output:
// maxSubarraySum([-2,1,-3,4,-1,2,1,-5,4]) → 6
// maxSubarraySum([-1,-2,-3])              → -1

// Array of 1 to N, one number repeating, one missing
// [1,2,2,4] from 1-4 → repeating=2, missing=3

public static void findRepeatMissing(int[] arr) {
    int n = arr.length;
    Map map = new HashMap<>();
    for (int x : arr) map.put(x, map.getOrDefault(x,0)+1);

    int repeating = -1, missing = -1;
    for (int i = 1; i <= n; i++) {
        int count = map.getOrDefault(i, 0);
        if (count == 2) repeating = i;   // appears twice = repeating
        if (count == 0) missing = i;     // never appears = missing
    }
    System.out.println("Repeating: " + repeating + ", Missing: " + missing);
}
// Output: findRepeatMissing([1,2,2,4]) → Repeating: 2, Missing: 3

// Bubble Sort: repeatedly compare adjacent elements and swap if out of order.
// After each full pass, the LARGEST unsorted element "bubbles up" to its correct position.
// Time: O(n²)   Space: O(1)

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {         // i = pass number (n-1 passes total)
        boolean swapped = false;                // optimization: stop early if no swaps
        for (int j = 0; j < n - 1 - i; j++) { // j goes up to (n-1-i) — last i are sorted
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];             // swap adjacent elements
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;  // if no swap in this pass → already sorted, stop early
    }
}

// DRY RUN for [5, 3, 8, 1, 2]:
// Pass 1 (i=0): compare all adjacent pairs
//   [5,3] → swap → [3,5,8,1,2]
//   [5,8] → ok
//   [8,1] → swap → [3,5,1,8,2]
//   [8,2] → swap → [3,5,1,2,8]   ← 8 is in its final position ✅
// Pass 2 (i=1):
//   [3,5] → ok
//   [5,1] → swap → [3,1,5,2,8]
//   [5,2] → swap → [3,1,2,5,8]   ← 5 is in final position ✅
// Pass 3 (i=2):
//   [3,1] → swap → [1,3,2,5,8]
//   [3,2] → swap → [1,2,3,5,8]   ← 3 in final position ✅
// Pass 4 (i=3): no swaps → done!
// Result: [1,2,3,5,8] ✅

// Output: bubbleSort([5,3,8,1,2]) → [1,2,3,5,8]

// Selection Sort: find the MINIMUM element in unsorted part, swap it to front.
// Each pass selects the correct element for position i.
// Time: O(n²)   Space: O(1)

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {          // i = position we're filling
        int minIdx = i;                          // assume position i has minimum
        for (int j = i + 1; j < n; j++) {       // search rest of array for smaller
            if (arr[j] < arr[minIdx]) {
                minIdx = j;                      // found a new minimum
            }
        }
        // swap minimum to position i
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

// DRY RUN for [64, 25, 12, 22, 11]:
// i=0: search [25,12,22,11] → min=11 at idx=4 → swap arr[0]↔arr[4]
//   → [11, 25, 12, 22, 64]   ← 11 placed ✅
// i=1: search [12,22,64] → min=12 at idx=2 → swap arr[1]↔arr[2]
//   → [11, 12, 25, 22, 64]   ← 12 placed ✅
// i=2: search [22,64] → min=22 at idx=3 → swap arr[2]↔arr[3]
//   → [11, 12, 22, 25, 64]   ← 22 placed ✅
// i=3: search [64] → min=25 at idx=3 → no swap needed
//   → [11, 12, 22, 25, 64]   ✅
// Result: [11,12,22,25,64] ✅

// Insertion Sort: like sorting playing cards in hand.
// Pick one card at a time and INSERT it into the correct position in the sorted part.
// Time: O(n²) worst, O(n) best (already sorted)   Space: O(1)

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {           // start from index 1 (first element is "sorted")
        int key = arr[i];                    // pick this element to insert
        int j = i - 1;                       // j points to end of sorted portion
        // shift all sorted elements greater than key one position right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];             // move element right
            j--;                             // move left
        }
        arr[j + 1] = key;                    // insert key at correct position
    }
}

// DRY RUN for [12, 11, 13, 5, 6]:
// i=1: key=11, arr=[12,11,13,5,6]
//   j=0: arr[0]=12 > 11 → shift: [12,12,13,5,6], j=-1
//   place key: arr[0]=11 → [11,12,13,5,6] ✅
// i=2: key=13
//   j=1: arr[1]=12 < 13 → stop
//   place key: arr[2]=13 → [11,12,13,5,6]  (no change)
// i=3: key=5
//   j=2: 13>5 shift → [11,12,13,13,6]
//   j=1: 12>5 shift → [11,12,12,13,6]
//   j=0: 11>5 shift → [11,11,12,13,6]
//   j=-1: stop. arr[0]=5 → [5,11,12,13,6] ✅
// i=4: key=6
//   j=3: 13>6 shift, j=2: 12>6 shift, j=1: 11>6 shift, j=0: 5<6 stop
//   arr[1]=6 → [5,6,11,12,13] ✅
// Result: [5,6,11,12,13] ✅

// Check EVERY element one by one until target found.
// Works on unsorted AND sorted arrays.
// Time: O(n)   Space: O(1)

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;  // found! return index
    }
    return -1;  // not found
}

// DRY RUN for arr=[10,25,7,43,1], target=43:
// i=0: arr[0]=10 ≠ 43
// i=1: arr[1]=25 ≠ 43
// i=2: arr[2]=7  ≠ 43
// i=3: arr[3]=43 = 43 → return 3 ✅

// Output:
// linearSearch([10,25,7,43,1], 43) → 3  (found at index 3)
// linearSearch([10,25,7,43,1], 99) → -1 (not found)

// Binary Search: ONLY works on SORTED arrays.
// Each step cuts the search space in HALF → much faster than linear!
// Time: O(log n)   Space: O(1)

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // safe mid: avoids integer overflow
        if (arr[mid] == target) return mid;   // found at mid!
        else if (arr[mid] < target) left = mid + 1;  // target is in RIGHT half
        else                        right = mid - 1; // target is in LEFT half
    }
    return -1;  // not found
}
// WHY left + (right-left)/2 instead of (left+right)/2?
// → Prevents integer overflow when left+right exceeds Integer.MAX_VALUE

// DRY RUN for arr=[1,3,5,7,9,11,13,15], target=7:
// left=0, right=7, mid=3, arr[3]=7 == 7 → return 3 ✅

// DRY RUN for target=11:
// left=0,right=7,mid=3: arr[3]=7 < 11 → left=4
// left=4,right=7,mid=5: arr[5]=11 == 11 → return 5 ✅

// Output:
// binarySearch([1,3,5,7,9,11,13], 7)  → 3
// binarySearch([1,3,5,7,9,11,13], 99) → -1

// Sorted array may have duplicates — find FIRST (leftmost) index of target
// [1,2,2,2,3,4] target=2 → first occurrence at index 1

public static int firstOccurrence(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = -1;           // store answer, start with "not found"
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;       // found a match — save it
            right = mid - 1;   // but keep searching LEFT for earlier occurrence
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}
// DRY RUN for [1,2,2,2,3,4], target=2:
// left=0,right=5,mid=2: arr[2]=2==2 → result=2, right=1
// left=0,right=1,mid=0: arr[0]=1<2 → left=1
// left=1,right=1,mid=1: arr[1]=2==2 → result=1, right=0
// left=1 > right=0 → stop
// Result: 1 ✅  (first 2 is at index 1)

// Find LAST (rightmost) index of target
// [1,2,2,2,3,4] target=2 → last occurrence at index 3

public static int lastOccurrence(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;       // found — save it
            left = mid + 1;    // keep searching RIGHT for later occurrence
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}
// DRY RUN for [1,2,2,2,3,4], target=2:
// mid=2: arr[2]=2==2 → result=2, left=3
// mid=4: arr[4]=3>2 → right=3
// mid=3: arr[3]=2==2 → result=3, left=4
// left=4>right=3 → stop
// Result: 3 ✅  (last 2 is at index 3)

// HashSet stores UNIQUE elements only — duplicates are automatically ignored
// [1,2,2,3,3,3,4] → {1,2,3,4}

public static void removeDupsHashSet(int[] arr) {
    Set set = new LinkedHashSet<>(); // LinkedHashSet preserves insertion order
    for (int n : arr) {
        set.add(n);  // if n already exists, add() does nothing (no error)
    }
    System.out.println("After removing duplicates: " + set);
}
// ITERATION for [1,2,2,3,3,3,4]:
// add(1) → set={1}
// add(2) → set={1,2}
// add(2) → already exists, ignored!
// add(3) → set={1,2,3}
// add(3) → ignored! add(3) → ignored!
// add(4) → set={1,2,3,4} ✅

// Converting back to array:
public static int[] toDedupedArray(int[] arr) {
    return Arrays.stream(arr).distinct().toArray(); // Java 8 stream
}

// Output:
// removeDupsHashSet([1,2,2,3,3,3,4]) → [1,2,3,4]

// Use Set's property: add() returns false if element already present

public static Set findDupsSet(int[] arr) {
    Set seen = new HashSet<>();
    Set duplicates = new LinkedHashSet<>();
    for (int n : arr) {
        if (!seen.add(n)) {    // add() returns false = already in set = DUPLICATE!
            duplicates.add(n);
        }
    }
    return duplicates;
}
// ITERATION for [1,3,4,2,2,3]:
// 1 → seen={1}, dup={}
// 3 → seen={1,3}, dup={}
// 4 → seen={1,3,4}, dup={}
// 2 → seen={1,3,4,2}, dup={}
// 2 → add returns false! dup={2}
// 3 → add returns false! dup={2,3}
// Result: {2,3} ✅

// Count how many times each element appears
// [a,b,a,c,b,a] → a→3, b→2, c→1

public static void countFreqMap(String[] arr) {
    Map map = new LinkedHashMap<>();
    for (String s : arr) {
        // getOrDefault: if key exists return its value, else return 0
        map.put(s, map.getOrDefault(s, 0) + 1);
    }
    for (Map.Entry e : map.entrySet()) {
        System.out.println(e.getKey() + " → " + e.getValue());
    }
}
// ITERATION for ["a","b","a","c","b","a"]:
// "a" → map={a:1}
// "b" → map={a:1, b:1}
// "a" → map={a:2, b:1}
// "c" → map={a:2, b:1, c:1}
// "b" → map={a:2, b:2, c:1}
// "a" → map={a:3, b:2, c:1} ✅

// Count frequencies using HashMap, then scan original string for count=1

public static char firstNonRepMap(String s) {
    Map map = new LinkedHashMap<>(); // LINKED preserves order!
    // Pass 1: build frequency map
    for (char c : s.toCharArray())
        map.put(c, map.getOrDefault(c, 0) + 1);
    // Pass 2: find first char with count=1
    for (char c : s.toCharArray())
        if (map.get(c) == 1) return c;
    return '_'; // all characters repeat
}
// WHY LinkedHashMap? Insertion order matters — we want the FIRST unique char.
// Regular HashMap doesn't guarantee order.

// DRY RUN for "swiss":
// map: s→3, w→1, i→1
// Scan "swiss": s→3 skip, w→1 → return 'w' ✅

// Output:
// firstNonRepMap("swiss")   → w
// firstNonRepMap("aabbcdd") → c

// int[] cannot use Collections directly — must use Integer[] or Arrays.asList

// For String/Integer arrays:
String[] arr = {"Java", "Python", "C++"};

// METHOD 1: Arrays.asList (Fast, but fixed-size — cannot add/remove)
List list1 = Arrays.asList(arr);

// METHOD 2: new ArrayList (Dynamic — can add/remove freely)
List list2 = new ArrayList<>(Arrays.asList(arr));
list2.add("Go");       // ✅ works
list2.remove("C++");   // ✅ works

// METHOD 3: Stream (Java 8 — for int[] specifically)
int[] nums = {1, 2, 3, 4, 5};
List intList = Arrays.stream(nums)
                               .boxed()           // int → Integer (autoboxing)
                               .collect(Collectors.toList());

// Output:
// list2 → [Java, Python, Go]   (after add and remove)

// Converting List to Set automatically removes duplicates!
List list = Arrays.asList(1, 2, 2, 3, 3, 3, 4);

// HashSet — no order guaranteed
Set hashSet = new HashSet<>(list);

// LinkedHashSet — preserves insertion order (usually preferred)
Set linkedSet = new LinkedHashSet<>(list);

// TreeSet — automatically sorts elements
Set treeSet = new TreeSet<>(list);

System.out.println("Original:   " + list);       // [1,2,2,3,3,3,4]
System.out.println("LinkedSet:  " + linkedSet);  // [1,2,3,4]
System.out.println("TreeSet:    " + treeSet);    // [1,2,3,4] (sorted)

List nums = Arrays.asList(5, 2, 8, 1, 9, 3);

// METHOD 1: Collections.sort — ascending (natural order)
Collections.sort(nums);
System.out.println("Ascending: " + nums);   // [1,2,3,5,8,9]

// METHOD 2: Collections.sort with Comparator — descending
Collections.sort(nums, Collections.reverseOrder());
System.out.println("Descending: " + nums);  // [9,8,5,3,2,1]

// METHOD 3: List.sort with lambda (Java 8)
nums.sort((a, b) -> a - b);  // ascending
nums.sort((a, b) -> b - a);  // descending

// Sorting list of Strings:
List words = Arrays.asList("banana","apple","cherry");
Collections.sort(words);
System.out.println(words); // [apple, banana, cherry]

// Sorting by length:
words.sort(Comparator.comparingInt(String::length));
System.out.println(words); // [apple, banana, cherry]

Map map = new LinkedHashMap<>();
map.put("Alice", 90);
map.put("Bob", 85);
map.put("Charlie", 92);

// METHOD 1: entrySet() — access both key AND value (Most common)
for (Map.Entry entry : map.entrySet()) {
    System.out.println(entry.getKey() + " → " + entry.getValue());
}

// METHOD 2: keySet() — access only keys, then get value
for (String key : map.keySet()) {
    System.out.println(key + " scored " + map.get(key));
}

// METHOD 3: values() — only values, no keys
for (int value : map.values()) {
    System.out.println(value);
}

// METHOD 4: forEach with lambda (Java 8 — cleanest)
map.forEach((key, value) -> System.out.println(key + ": " + value));

// Output (METHOD 1):
// Alice → 90
// Bob → 85
// Charlie → 92

// Recursion idea: print N AFTER calling for N-1
// We go DEEP first (base case), then print on the way BACK UP

public static void print1toN(int n) {
    if (n == 0) return;       // BASE CASE: stop recursion when n=0
    print1toN(n - 1);         // recursive call with n-1 FIRST
    System.out.print(n + " "); // print AFTER returning from recursion
}
// WHY print AFTER the call? Because we want 1 printed before 2, 3, etc.
// The call goes deep (n=3 → 2 → 1 → 0), then prints while returning (1, 2, 3)

// CALL STACK for n=3:
// print1toN(3) → calls print1toN(2)
//   print1toN(2) → calls print1toN(1)
//     print1toN(1) → calls print1toN(0)
//       print1toN(0) → returns (base case)
//     ← prints 1
//   ← prints 2
// ← prints 3
// Output: 1 2 3 ✅

// Print BEFORE the recursive call → print on the way DOWN

public static void printNto1(int n) {
    if (n == 0) return;        // BASE CASE
    System.out.print(n + " "); // print FIRST (before calling)
    printNto1(n - 1);          // then recurse with n-1
}
// CALL STACK for n=3:
// printNto1(3): print 3 → calls printNto1(2)
//   printNto1(2): print 2 → calls printNto1(1)
//     printNto1(1): print 1 → calls printNto1(0)
//       printNto1(0): return (base case)
// Output: 3 2 1 ✅

// KEY DIFFERENCE from RE1:
// RE1 (1 to N): print AFTER recursive call → numbers print smallest first
// RE2 (N to 1): print BEFORE recursive call → numbers print largest first

// n! = n × (n-1)!    with base case: 0! = 1  and  1! = 1

public static long factRec(int n) {
    if (n == 0 || n == 1) return 1;   // BASE CASE: stop here
    return n * factRec(n - 1);         // RECURSIVE CASE: n × factorial(n-1)
}

// CALL STACK for n=5:
// factRec(5) = 5 × factRec(4)
//              5 × 4 × factRec(3)
//              5 × 4 × 3 × factRec(2)
//              5 × 4 × 3 × 2 × factRec(1)
//              5 × 4 × 3 × 2 × 1          ← base case returns 1
// UNWINDING the stack:
//   factRec(1) = 1
//   factRec(2) = 2×1 = 2
//   factRec(3) = 3×2 = 6
//   factRec(4) = 4×6 = 24
//   factRec(5) = 5×24 = 120 ✅

// Output: factRec(5) → 120    factRec(0) → 1

// fib(n) = fib(n-1) + fib(n-2)    base cases: fib(0)=0, fib(1)=1

public static int fibRec(int n) {
    if (n == 0) return 0;             // BASE CASE 1
    if (n == 1) return 1;             // BASE CASE 2
    return fibRec(n - 1) + fibRec(n - 2); // RECURSIVE CASE
}

// CALL TREE for fibRec(4):
//           fib(4)
//          /       \
//       fib(3)    fib(2)
//       /    \    /    \
//    fib(2) fib(1) fib(1) fib(0)
//    /    \
// fib(1) fib(0)
// = (1+0) + 1 + 1 + 0 = ... = 3 ✅

// ⚠️ Recursive fibonacci is O(2^n) — very slow for large n!
// Use iterative version for n > 30.

// Output:
// fibRec(0)→0  fibRec(1)→1  fibRec(5)→5  fibRec(7)→13

// Compare characters from both ends, move inward recursively

public static boolean isPalinRec(String s, int left, int right) {
    if (left >= right) return true;           // BASE CASE: pointers met or crossed
    if (s.charAt(left) != s.charAt(right)) return false; // mismatch → not palindrome
    return isPalinRec(s, left + 1, right - 1); // move both pointers inward
}

// Helper method to call easily:
public static boolean isPalindrome(String s) {
    return isPalinRec(s.toLowerCase(), 0, s.length() - 1);
}

// CALL STACK for "racecar":
// isPalinRec("racecar", 0, 6): r==r ✅ → call(1,5)
//   call(1,5): a==a ✅ → call(2,4)
//     call(2,4): c==c ✅ → call(3,3)
//       call(3,3): left(3) >= right(3) → return true (BASE CASE)
//     ← returns true
//   ← returns true
// ← returns true ✅

// Output:
// isPalindrome("racecar") → true    isPalindrome("hello") → false

// For n=5, output:
// *
// * *
// * * *
// * * * *
// * * * * *

// Logic: Row i → print i stars (i goes from 1 to n)
public static void rightTriangle(int n) {
    for (int i = 1; i <= n; i++) {          // outer loop: each row
        for (int j = 1; j <= i; j++) {      // inner loop: print i stars
            System.out.print("* ");
        }
        System.out.println();               // move to next line after each row
    }
}

// ITERATION TABLE for n=4:
// Row i=1: j runs 1 to 1 → print 1 star  → *
// Row i=2: j runs 1 to 2 → print 2 stars → * *
// Row i=3: j runs 1 to 3 → print 3 stars → * * *
// Row i=4: j runs 1 to 4 → print 4 stars → * * * *

// For n=5, output:
// * * * * *
// * * * *
// * * *
// * *
// *

// Logic: Row i → print (n - i + 1) stars
public static void reverseTriangle(int n) {
    for (int i = n; i >= 1; i--) {          // outer loop: starts from n, goes down to 1
        for (int j = 1; j <= i; j++) {      // inner loop: print i stars
            System.out.print("* ");
        }
        System.out.println();
    }
}

// ITERATION TABLE for n=4:
// Row i=4: print 4 stars → * * * *
// Row i=3: print 3 stars → * * *
// Row i=2: print 2 stars → * *
// Row i=1: print 1 star  → *

// For n=4, output:
//    *
//   * *
//  * * *
// * * * *
// (spaces before stars to center them)

// Logic: Each row i has (n-i) spaces then i stars
public static void pyramid(int n) {
    for (int i = 1; i <= n; i++) {
        // print leading spaces: (n-i) spaces for row i
        for (int j = 1; j <= n - i; j++) {
            System.out.print(" ");
        }
        // print stars: i stars for row i
        for (int j = 1; j <= i; j++) {
            System.out.print("* ");
        }
        System.out.println();
    }
}

// ITERATION TABLE for n=4:
// i=1: 3 spaces, 1 star  →    *
// i=2: 2 spaces, 2 stars →   * *
// i=3: 1 space,  3 stars →  * * *
// i=4: 0 spaces, 4 stars → * * * *

// For n=4, output:
// 1
// 1 2
// 1 2 3
// 1 2 3 4

// Logic: In row i, print numbers 1 through i
public static void numberPyramid(int n) {
    for (int i = 1; i <= n; i++) {          // outer loop: each row
        for (int j = 1; j <= i; j++) {      // inner loop: print 1 to i
            System.out.print(j + " ");
        }
        System.out.println();
    }
}

// ITERATION TABLE for n=4:
// i=1: j=1       → 1
// i=2: j=1,2     → 1 2
// i=3: j=1,2,3   → 1 2 3
// i=4: j=1,2,3,4 → 1 2 3 4

// BONUS — Floyd's Triangle (continuous numbers):
// 1
// 2 3
// 4 5 6
public static void floydsTriangle(int n) {
    int num = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) System.out.print(num++ + " ");
        System.out.println();
    }
}