DSA Day 2: Solving Our First Basic Java Problems

Welcome to Day 2 of my Data Structures and Algorithms (DSA) journey! In Day 1, we established the foundational syntax of Java: input/output, primitive data types, conditionals, loops, and the mechanics of parameter passing (Pass-by-Value vs. References).

At the end of Day 1, we defined three action items to practice these concepts. Today, we will write the solutions for these problems, discuss key Java concepts like integer overflow and String immutability, and analyze their Time and Space complexity.

Let’s dive in!

---

1. Find Factorial (Loop-based)

The factorial of a non-negative integer $n$ (denoted as $n!$) is the product of all positive integers less than or equal to $n$. Mathematically: \(n! = n \times (n-1) \times (n-2) \times \dots \times 1\) By definition, $0! = 1$.

Logic & Implementation

To calculate the factorial, we can use a loop (either for or while) starting from $1$ up to $n$, multiplying a running product variable on each iteration.

Critical Concern: Integer Overflow

A common pitfall in Java is using a standard int (32-bit signed integer) for the product. Factorial grows extremely fast:

• $12! = 479,001,600$ (fits in int)
• $13! = 6,227,020,800$ (exceeds Integer.MAX_VALUE of $2,147,483,647$)

If we use int, calculating $13!$ will result in overflow and produce a garbage negative number. To mitigate this, we should use a long (64-bit signed integer), which can safely store up to $20!$.

public class FactorialCalculator {
    public static long calculateFactorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Factorial is not defined for negative numbers.");
        }
        
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    public static void main(String[] args) {
        int number = 15;
        System.out.println("Factorial of " + number + " is: " + calculateFactorial(number));
        // Output: Factorial of 15 is: 1307674368000
    }
}

Complexity Analysis

• Time Complexity: $O(n)$ — The loop runs exactly $n$ times.
• Space Complexity: $O(1)$ — We only use a fixed amount of memory (the variable result and loop iterator i).

---

2. Reverse a String (Character-by-Character)

The task is to take a string and construct a new string by reading characters backward from the end to the beginning.

Logic & Implementation

We can iterate through the input string starting from index length - 1 down to 0. On each step, we retrieve the character at the current index and append it to our accumulator.

Critical Concern: String Immutability

In Java, String objects are immutable. Every time you perform a concatenation like reversed = reversed + str.charAt(i), Java does not modify the existing string. Instead, it:

1. Creates a temporary StringBuilder object.
2. Appends the existing string and the new character.
3. Converts it back to a new String object.

Doing this inside a loop of size $n$ creates $O(n)$ temporary objects and copies characters repeatedly, leading to a quadratic time complexity of $O(n^2)$.

To write an efficient $O(n)$ solution, we must use a StringBuilder, which represents a mutable sequence of characters.

public class StringReversal {
    public static String reverseString(String input) {
        if (input == null) {
            return null;
        }

        StringBuilder reversed = new StringBuilder();
        // Read character-by-character backward
        for (int i = input.length() - 1; i >= 0; i--) {
            reversed.append(input.charAt(i));
        }

        return reversed.toString();
    }

    public static void main(String[] args) {
        String original = "JavaBasics";
        String reversed = reverseString(original);
        System.out.println("Original: " + original);
        System.out.println("Reversed: " + reversed);
        // Output: Reversed: scisaBavaJ
    }
}

Complexity Analysis

• Time Complexity: $O(n)$ — We iterate through the string of length $n$ once, and StringBuilder.append() takes $O(1)$ amortized time.
• Space Complexity: $O(n)$ — The StringBuilder stores the $n$ characters of the reversed string.

---

3. Swap Two Variables (Using Reference Types)

In Day 1, we learned that Java is strictly Pass-by-Value. If you attempt to write a naive swap helper function:

public static void naiveSwap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}

And call it like naiveSwap(x, y), the values of x and y in the calling method do not change. This is because Java passes a copy of the primitive values, and the modification only happens to local parameters on the stack frame of naiveSwap.

Logic & Implementation

To allow a method to swap two variables and have those changes reflect in the caller’s frame, we must use a reference type (such as an array or a wrapper object).

When we pass an array to a method, a copy of the reference (memory address) is passed. Because the reference points to the same object on the heap, modifications to the array elements are visible to the caller.

Let’s look at two standard ways to implement this.

Method A: Swapping elements inside an existing array

This is the most common swap helper function used in algorithms (like sorting). We pass the array and the indices of the elements we want to swap.

import java.util.Arrays;

public class ArrayElementSwap {
    public static void swap(int[] arr, int index1, int index2) {
        // Swap array elements using a temporary variable
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {10, 20, 30, 40};
        System.out.println("Before swap: " + Arrays.toString(nums));
        
        // Swap element at index 1 (20) and index 2 (30)
        swap(nums, 1, 2);
        
        System.out.println("After swap:  " + Arrays.toString(nums));
        // Output: [10, 30, 20, 40]
    }
}

Method B: Swapping two variables using a wrapper array

If we have two distinct variables that we want to swap using a function, we can pack them into a 2-element array wrapper, pass the array to our swap helper, and unpack them afterward.

import java.util.Arrays;

public class VariableSwapWrapper {
    public static void swap(int[] wrapper) {
        if (wrapper == null || wrapper.length < 2) {
            return;
        }
        int temp = wrapper[0];
        wrapper[0] = wrapper[1];
        wrapper[1] = temp;
    }

    public static void main(String[] args) {
        int x = 5;
        int y = 99;
        
        // Wrap variables into an array
        int[] wrapper = {x, y};
        
        System.out.println("Before swap: x = " + wrapper[0] + ", y = " + wrapper[1]);
        
        // Pass reference of the wrapper to the helper
        swap(wrapper);
        
        // Unpack swapped values back to variables
        x = wrapper[0];
        y = wrapper[1];
        
        System.out.println("After swap:  x = " + x + ", y = " + y);
        // Output: x = 99, y = 5
    }
}

Memory Visual representation

When swap(wrapper) is called:

1. main creates an array {5, 99} on the heap. Let’s say it’s at address 0x100. The variable wrapper in main stores 0x100.
2. When calling swap(wrapper), a copy of 0x100 is passed to the parameter variable wrapper in the swap method.
3. Both variables point to the same memory on the heap.
4. swap modifies indices 0 and 1 on 0x100.
5. When swap returns and its stack frame is popped, the changes to 0x100 persist, and main reads the updated values.

---

🏁 Day 2 Summary & What’s Next

By solving these three basic problems, we’ve practiced:

1. Loop control flow and being mindful of data types & overflows (int vs long).
2. String manipulation while avoiding performance bottlenecks caused by String immutability (using StringBuilder).
3. Reference types and parameter passing, understanding how array arguments are reference copies that let us mutate objects.

Now that we have these foundations down, we are ready to analyze the efficiency of our code!

In Day 3, we will cover Time and Space Complexity (Big O notation) and dive deep into Array operations and search/sort algorithms. Stay tuned!