Java For Competitive Programming

🔣 Data Types, Conditional Stmts, Operators and Loops

Data types are important because they determine what kind of data you can store, how much memory it uses, and what range of values it can handle.

For competitive coding, choosing the correct data type helps you:

Example: If a problem says n ≤ 10⁹, int may be enough, but calculations like n × n can reach 10¹⁸, so long is safer.

👉 Rule: In competitive coding, always check constraints before choosing a data type.

Reference Diagram (Click image to view/download full resolution)

Java Data Types Diagram

🔄 Typecasting & Data Conversions

In Java, Typecasting is the process of converting a value from one data type to another. Mastering both Implicit (Widening) and Explicit (Narrowing) conversions is essential for mathematical accuracy, preventing hidden logic bugs, and avoiding runtime errors.

Why Data Conversions Matter in Competitive Coding & Math

Reference Diagram (Click image to view/download full resolution)

Java Typecasting Diagram

🛠️ Java Important Library Functions (Math, Strings, Arrays & Collections)

Java library functions provide pre-built, optimized methods for common tasks, allowing you to solve problems faster and write cleaner code.

👉 Rule: In competitive coding, know commonly used Java library functions and their asymptotic time complexities.

Reference Diagram (Click image to view/download full resolution)

  Java Built-in Libraries and Methods Cheat Sheet

📊 Java Arrays

Arrays are one of the most fundamental data structures in competitive coding. They allow you to store and efficiently access multiple values using an index.

  

👉 Rule: In competitive coding, master array indexing, traversal, searching, sorting, and common multi-pointer techniques thoroughly.


Reference Diagram (Click image to view/download full resolution)

--- Java Typecasting Diagram

🧰 Java Collections Framework

The Java Collections Framework provides a set of interfaces and classes for storing, organizing, and manipulating groups of objects efficiently. It is essential for competitive coding because it provides ready-to-use data structures with optimized operations.

👉 Rule: In competitive coding, understand when to use ArrayList, HashSet, LinkedHashSet, TreeSet, HashMap, LinkedHashMap, and TreeMap based on ordering, uniqueness, sorting, and time-complexity requirements.

Key Collections at a Glance


Reference Diagram (Click image to view/download full resolution)

Java Collections Framework Important Classes

⏱️ Time and Space Complexity

Time and space complexity are important because they help us understand how efficiently program performs as the input size grows.

For competitive coding, understanding complexity helps you:

Time Complexity: describes how the running time or number of operations of an algorithm grows with respect to the input size n.

Space Complexity: describes how much additional memory an algorithm requires as the input size n grows.

Example: If an algorithm checks every element of an array once, it performs approximately n operations, giving it O(n) time complexity. If another algorithm uses a nested loop to compare every pair of elements, it may perform approximately n × n operations, giving it O(n²) time complexity.

Similarly, if an algorithm creates an additional array of size n, its extra space requirement is O(n).

👉 Rule: In competitive coding, always consider both time complexity and space complexity before choosing an approach. Your approach must be efficient enough to satisfy the problem's time and memory limits.

📄 PDF material for time complexity

📥 Click here to view/download

🧱 Subarray, Subsequence and Subset

Subarray, subsequence, and subset are fundamental concepts in competitive programming. Understanding the difference between them is important because the techniques and algorithms used to solve problems can be very different.

For competitive coding, understanding these concepts helps you:

Subarray

A subarray is a contiguous part of an array. All elements between the starting and ending positions are included.

Example: Consider the array:

[1, 2, 3]

All possible non-empty subarrays are:

  1. [1]
  2. [2]
  3. [3]
  4. [1, 2]
  5. [2, 3]
  6. [1, 2, 3]

Notice that [1, 3] is not a subarray because 1 and 3 are not contiguous.

For an array of size n, the total number of non-empty subarrays is:

n × (n + 1) / 2

For n = 3:

3 × 4 / 2 = 6

Common techniques:

Subsequence

A subsequence is obtained by deleting zero or more elements from an array while maintaining the relative order of the remaining elements.

Example: Consider the array:

[1, 2, 3]

All possible subsequences are:

  1. []
  2. [1]
  3. [2]
  4. [3]
  5. [1, 2]
  6. [1, 3]
  7. [2, 3]
  8. [1, 2, 3]

Notice that [1, 3] is a valid subsequence even though the elements are not contiguous.

However, [3, 1] is not a subsequence because the original order of the elements is not preserved.

For an array of size n, the total number of possible subsequences, including the empty subsequence, is:

2n

For n = 3:

23 = 8

If the empty subsequence is excluded:

2n − 1 = 7

Common techniques:

Subset

A subset is a collection of elements selected from a set where the order of elements does not matter.

Example: Consider the set:

{1, 2, 3}

All possible subsets are:

  1. {}
  2. {1}
  3. {2}
  4. {3}
  5. {1, 2}
  6. {1, 3}
  7. {2, 3}
  8. {1, 2, 3}

In a subset, {1, 3} and {3, 1} represent the same subset because order does not matter.

For a set containing n distinct elements, the total number of subsets, including the empty subset, is:

2n

For n = 3:

23 = 8

Common techniques:

👉 Rule: First identify whether the problem deals with a subarray, subsequence, or subset. Then choose the technique based on whether elements must be contiguous, whether their order matters, and the constraints on n.

🚀 Sliding Window, Prefix Sum and Two Pointers

Sliding Window, Prefix Sum, and Two Pointers are common problem-solving techniques used extensively in array and string problems. Choosing the correct technique can help reduce a solution from O(n²) or O(n³) to O(n) or O(n log n).

Understanding these techniques helps you:

Sliding Window

Sliding Window is a technique used to process a contiguous portion of an array or string while efficiently moving the range from left to right.

Instead of recalculating the result for every possible subarray, we maintain a window using two boundaries, usually represented by left and right.

Example:

[1, 2, 3, 4, 5]

Suppose we want the sum of every subarray of size 3.

[1, 2, 3] → sum = 6

Instead of calculating the next window from scratch:

[2, 3, 4] → 2 + 3 + 4 = 9

We remove the element leaving the window and add the new element:

6 − 1 + 4 = 9

This allows each element to be processed only a small number of times.

Common types:

Common problems:

Typical complexity:

O(n) time and O(1) or O(k) auxiliary space depending on the problem.

Prefix Sum

Prefix Sum is a technique used to preprocess an array so that the sum of elements in any range can be calculated efficiently.

The first step is to create a prefix sum array. Each element of the prefix array stores the sum of all elements from the beginning of the original array up to that index.

Example:

arr = [1, 2, 3, 4, 5]

We create a prefix array prefix of the same size:

prefix = [_, _, _, _, _]

Step 1: First element:

prefix[0] = arr[0] = 1

prefix = [1, _, _, _, _]

Step 2: Add the current element to the previous prefix sum:

prefix[1] = prefix[0] + arr[1]
= 1 + 2 = 3

prefix = [1, 3, _, _, _]

Step 3:

prefix[2] = prefix[1] + arr[2]
= 3 + 3 = 6

prefix = [1, 3, 6, _, _]

Step 4:

prefix[3] = prefix[2] + arr[3]
= 6 + 4 = 10

prefix = [1, 3, 6, 10, _]

Step 5:

prefix[4] = prefix[3] + arr[4]
= 10 + 5 = 15

prefix = [1, 3, 6, 10, 15]

Therefore, the final prefix sum array is:

[1, 3, 6, 10, 15]

The general formula is:

prefix[i] = prefix[i - 1] + arr[i]

So each prefix value represents the sum from index 0 to index i.

prefix[2] = 1 + 2 + 3 = 6
prefix[4] = 1 + 2 + 3 + 4 + 5 = 15

📌 Range Sum Using Prefix Sum

Once the prefix array is created, we can calculate the sum of any contiguous range efficiently.

Consider the same array:

arr = [1, 2, 3, 4, 5]

and its prefix array:

prefix = [1, 3, 6, 10, 15]

Suppose we want to find the sum of the elements from index 1 to index 3:

[2, 3, 4]

Direct calculation gives:

2 + 3 + 4 = 9

Using the prefix array, we already know:

prefix[3] = 1 + 2 + 3 + 4 = 10

But this also includes the element before our range:

arr[0] = 1

So we subtract prefix[0]:

Range Sum(1, 3) = prefix[3] − prefix[0]

= 10 − 1 = 9

Therefore:

Sum of indices [1, 3] = 9

General Range Formula

For a range [l, r]:

Sum(l, r) = prefix[r] − prefix[l − 1]

However, when l = 0, there is no element before the range. Therefore:

Sum(0, r) = prefix[r]

Example: Find the sum from index 0 to 3:

1 + 2 + 3 + 4 = 10

Sum(0, 3) = prefix[3] = 10

After preprocessing, each range-sum query can be answered in O(1) time.

Common applications:

Two Pointers

Two Pointers is a technique where two indices are used to traverse an array or string efficiently. The pointers are commonly called left and right.

The pointers may move toward each other, move in the same direction, or represent the boundaries of a range.

Example:

arr = [1, 2, 3, 4, 6]

Suppose the array is sorted and we want to find whether two elements have a sum equal to 6.

left = 0,   right = 4

Calculate:

arr[left] + arr[right] = 1 + 6 = 7

Since the sum is greater than 6, move the right pointer left.

1 + 4 = 5

Now the sum is smaller than 6, so move the left pointer right.

2 + 4 = 6

The required pair is found.

Common patterns:

Common problems:

Typical complexity:

O(n) time with O(1) auxiliary space for many two-pointer problems.

How to Choose the Technique?

⚙️ Functions and Recursion

Functions and Recursion are fundamental programming concepts used to organize code, avoid repetition, and solve problems by breaking them into smaller parts.

In competitive programming, functions help us write reusable and modular code, while recursion is especially useful for problems involving trees, graphs, backtracking, divide and conquer, and repeated subproblems.

Understanding these concepts helps you:

Functions

A function is a block of code designed to perform a specific task. Instead of writing the same code repeatedly, we can place it inside a function and call it whenever required.

Basic Java syntax:

returnType functionName(parameters) {
    // statements
    return value;
}

Example:

static int add(int a, int b) {
    return a + b;
}

The function above takes two integers as input and returns their sum.

Calling the function:

int result = add(10, 20);

System.out.println(result);

📌 Parts of a Function

Consider:

static int multiply(int a, int b) {
    return a * b;
}

🔢 Types of Functions

Functions can be categorized based on whether they take parameters and return a value.

  1. No parameters, no return value
  2. Parameters, no return value
  3. No parameters, returns a value
  4. Parameters and returns a value

Example:

// No parameter, no return value
static void greet() {
    System.out.println("Hello");
}

// Parameters, no return value
static void printSum(int a, int b) {
    System.out.println(a + b);
}

// No parameter, returns a value
static int getNumber() {
    return 10;
}

// Parameters and returns a value
static int add(int a, int b) {
    return a + b;
}

🔄 Recursion

Recursion is a technique in which a function calls itself to solve a smaller version of the same problem.

A recursive solution generally contains two important parts:

Example: Factorial

The factorial of a number n is:

n! = n × (n − 1) × (n − 2) × ... × 1

For example:

5! = 5 × 4 × 3 × 2 × 1 = 120

We can express factorial recursively as:

n! = n × (n − 1)!

The base case is:

0! = 1

Recursive implementation:

static int factorial(int n) {

    // Base Case
    if (n == 0) {
        return 1;
    }

    // Recursive Case
    return n * factorial(n - 1);
}

🔍How Recursion Works

Consider: 

factorial(5)

The calls are:

factorial(5)
↓
5 × factorial(4)
↓
5 × 4 × factorial(3)
↓
5 × 4 × 3 × factorial(2)
↓
5 × 4 × 3 × 2 × factorial(1)
↓
5 × 4 × 3 × 2 × 1 × factorial(0)

At factorial(0), the base case returns 1. The pending function calls then return in reverse order.

1 → 1 → 2 → 6 → 24 → 120

📚 Recursion and the Call Stack

Every function call is stored in the program's call stack until the function finishes execution.

For: 

factorial(3)

The stack grows like:

factorial(3)
    ↓
factorial(2)
    ↓
factorial(1)
    ↓
factorial(0)

Once the base case is reached, the calls are completed in reverse order: 

factorial(0)
    ↑
factorial(1)
    ↑
factorial(2)
    ↑
factorial(3)

Therefore, recursion uses additional memory for the call stack.

Example: Sum of Numbers

Find the sum of numbers from 1 to n.

For n = 5:

1 + 2 + 3 + 4 + 5 = 15

We can define:

sum(n) = n + sum(n − 1)

with the base case:

sum(0) = 0 

static int sum(int n) {

    // Base Case
    if (n == 0) {
        return 0;
    }

    // Recursive Case
    return n + sum(n - 1);
}

Example: Print Array Using Recursion

Recursion can also be used to traverse an array. 

static void printArray(int[] arr, int index) {

    // Base Case
    if (index == arr.length) {
        return;
    }

    System.out.println(arr[index]);

    // Recursive Case
    printArray(arr, index + 1);
}

For:

[10, 20, 30, 40]

The recursive calls are:

index = 0 → 1 → 2 → 3 → 4

When index == arr.length, the recursion stops.

🔁 Recursion with Multiple Calls

A function can also make more than one recursive call. This creates a recursion tree.

Example: Fibonacci

F(n) = F(n − 1) + F(n − 2)

with:

F(0) = 0     F(1) = 1 

static int fibonacci(int n) {

    if (n <= 1) {
        return n;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

This simple recursive implementation has overlapping subproblems and becomes inefficient for larger values of n. This is one reason Dynamic Programming is often used to optimize recursive solutions.

Recursion in Competitive Programming

Recursion is commonly used for:

⚠️ Important Points

Be Careful with Time and Space Complexity while working with recursion

The complexity of a recursive solution depends on the number of recursive calls and the amount of work performed at each call.

Example: Factorial

Rule:

👉 Before writing a recursive solution, identify the base case, determine the smaller subproblem, and understand how the current answer is built from the recursive result.

🔀 Bit Manipulation

What is Bit Manipulation?

Bit Manipulation is the technique of directly working with the individual bits of an integer using bitwise operators. Since integers are stored in binary form, bit manipulation allows us to perform many operations efficiently and faster compared to arithmetic operations.

⚙️ Bitwise Operators in Java

Operator Name Example Result Meaning
& AND 5 & 3 1 1 only when both bits are 1
| OR 5 | 3 7 1 when at least one bit is 1
^ XOR 5 ^ 3 6 1 when bits are different
~ NOT ~5 -6 Flips every bit
<< Left Shift 5 << 1 10 Shifts bits to the left
>> Signed Right Shift 5 >> 1 2 Shifts bits right while preserving sign
>>> Unsigned Right Shift 5 >>> 1 2 Shifts bits right and fills with 0

Binary Representation

Every integer can be represented using powers of 2. 

13 = 1101

13 = 1×2³ + 1×2² + 0×2¹ + 1×2⁰
   = 8 + 4 + 0 + 1
   = 13

For an integer n, the bit at position i represents: 

2^i

Bit positions start from 0 at the rightmost bit. 

13 = 1101
     ↓↓↓↓
Position
     3210

🔑 Important Bit Manipulation Formulas

1️⃣ Check if the i-th Bit is Set

(n & (1 << i)) != 0

Example: 

n = 13 = 1101

Check bit 2:

1 << 2 = 0100

  1101
& 0100
-------
  0100

Result is non-zero → Bit 2 is SET

2️⃣ Set the i-th Bit

Setting a bit means changing it to 1. 

n | (1 << i)

Example: 

n = 1001
i = 1

1 << 1 = 0010

  1001
| 0010
-------
  1011

3️⃣ Clear the i-th Bit

Clearing a bit means changing it to 0. 

n & ~(1 << i)

Example: 

n = 1111
i = 2

1 << 2 = 0100

  1111
& 1011
-------
  1011

4️⃣ Toggle the i-th Bit

Toggle changes: 

n ^ (1 << i)

Example: 

n = 1001
i = 1

  1001
^ 0010
-------
  1011

5️⃣ Remove the Lowest Set Bit

One of the most important bit tricks: 

n & (n - 1)

Example: 

n     = 101100
n - 1 = 101011

  101100
& 101011
---------
  101000

The rightmost 1 is removed.

6️⃣ Extract the Lowest Set Bit

n & -n

Example: 

n = 101100

n & -n

= 000100

Therefore, n & -n gives the value represented by the lowest set bit.

7️⃣ Check if a Number is Odd or Even

The rightmost bit determines whether a number is odd or even. 

n & 1
Number Binary n & 1 Type
5 101 1 Odd
8 1000 0 Even

8️⃣ Check if a Number is a Power of 2

A positive power of 2 contains exactly one set bit. 

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

Examples: 

1  = 0001  → Power of 2
2  = 0010  → Power of 2
4  = 0100  → Power of 2
8  = 1000  → Power of 2
16 = 10000 → Power of 2

12 = 1100 → Not a power of 2

⚡ Shift Operators

⬅️ Left Shift

n << k

For positive integers where overflow does not occur: 

n << k = n × 2^k

Example: 

5 << 2

101 << 2
= 10100
= 20

➡️ Right Shift

n >> k

For positive integers: 

n >> k = n / 2^k

Example: 

20 >> 2

10100 >> 2
= 00101
= 5

XOR Properties

XOR is one of the most important operators in competitive programming.

Example: 

5 ^ 7 ^ 5

= (5 ^ 5) ^ 7
= 0 ^ 7
= 7

The two occurrences of 5 cancel each other.

Technique 1: Count Set Bits

A set bit is a bit whose value is 1.

Example: 

13 = 1101

Set bits:
1 + 0 + 1 + 1

Number of set bits = 3

The important trick is: 

n & (n - 1)

which removes exactly one set bit. Therefore, repeatedly applying this operation allows us to count the number of set bits.

Technique 2: Find the Unique Element Using XOR

If every element appears exactly twice except one element, XOR can find the unique element.

Example: 

[4, 1, 2, 1, 2]

4 ^ 1 ^ 2 ^ 1 ^ 2

= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

The duplicate elements cancel because: 

x ^ x = 0

🔢 Technique 3: Generate All Subsets Using Bitmasking

For an array of n elements, the number of possible subsets is: 

2^n

Each subset can be represented using an n-bit mask.

Example: 

arr = [10, 20, 30]
Mask Selected Elements
000 { }
001 {10}
010 {20}
011 {10, 20}
100 {30}
101 {10, 30}
110 {20, 30}
111 {10, 20, 30}

For example: 

Mask = 101

Bit 0 → 1 → Select 10
Bit 1 → 0 → Don't select 20
Bit 2 → 1 → Select 30

Subset = {10, 30}

This technique is called Bitmasking.