Data Structures and Algorithms in Java

What is a Data Structure?

A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently.

Why Use Data Structures? Because they help in:

  • Efficient data access
  • Memory management
  • Speeding up processing

Real-life Example: Think of a data structure like a bookshelf. You can organize books (data) in rows, by category (array, stack, etc.), so it’s easier to find and use them quickly.

What is an Algorithm?

An algorithm is a step-by-step procedure to solve a problem or perform a computation.

Why Use Algorithms?

  • To solve problems efficiently
  • To automate processes
  • To improve time and space performance

Real-life Example: Making tea. Your algorithm could be:
1. Boil water
2. Add tea leaves
3. Pour into a cup
4. Add sugar/milk

Why Learn DSA with Java?
  • Java provides built-in libraries for many data structures.
  • Object-Oriented approach makes code reusable and scalable.
  • Popular in job interviews and competitive programming.
Topics Covered in Data Structures
  • Arrays
  • Linked Lists
  • Stacks and Queues
  • Trees and Graphs
  • Hashing
Topics Covered in Algorithms
  • Searching and Sorting
  • Recursion and Backtracking
  • Dynamic Programming
  • Greedy Algorithms
  • Graph Algorithms (DFS, BFS, Dijkstra)
Arrays

When to Use: When you need fast access using index and a fixed-size collection.

Why: Simple structure with O(1) access time.

Real-life Example: Seats in a theater — fixed position, numbered.

int[] numbers = {1, 2, 3, 4}; System.out.println(numbers[2]); // Output: 3
Linked List

When to Use: When frequent insertion/deletion is required.

Why: No need to shift elements; dynamic size.

Real-life Example: Train compartments linked together.

class Node { int data; Node next; Node(int d) { data = d; next = null; } }
Stack

When to Use: When you need Last-In-First-Out (LIFO) behavior.

Why: Ideal for undo operations, expression parsing, etc.

Real-life Example: Stack of plates.

Stack stack = new Stack<>(); stack.push(10); stack.push(20); System.out.println(stack.pop()); // Output: 20
Queue

When to Use: First-In-First-Out (FIFO) scenarios like print queues.

Why: Useful in scheduling and buffering.

Real-life Example: People standing in line.

Queue<Integer> queue = new LinkedList<>(); queue.add(1); queue.add(2); System.out.println(queue.remove()); // Output: 1
HashMap

When to Use: When you need fast lookup using keys.

Why: Offers O(1) average time for get/put.

Real-life Example: Dictionary (word → meaning).

Map<String, String> map = new HashMap<>(); map.put("name", "Alice"); System.out.println(map.get("name")); // Output: Alice
Tree

When to Use: To maintain hierarchical data (e.g., file system, DOM).

Why: Efficient searching, insertion, traversal.

Real-life Example: Organization chart or folder structure.

class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } }
Graph

When to Use: When dealing with networks, routes, social connections.

Why: Models complex relationships effectively.

Real-life Example: Google Maps, Facebook friends.

Map<Integer, List<Integer>> graph = new HashMap<>(); graph.put(0, Arrays.asList(1, 2));
Time Complexity

Definition: Time complexity is a measure of the time an algorithm takes to run as a function of the input size.

Why It Matters: Helps estimate performance and scalability of algorithms.

Common Time Complexities:

  • O(1) – Constant Time (e.g., accessing array element)
  • O(log n) – Logarithmic Time (e.g., binary search)
  • O(n) – Linear Time (e.g., traversing an array)
  • O(n log n) – Linearithmic Time (e.g., merge sort)
  • O(n²) – Quadratic Time (e.g., bubble sort)
  • O(2ⁿ) – Exponential Time (e.g., recursive Fibonacci)
  • O(n!) – Factorial Time (e.g., permutations)

Real-Life Examples:

  • O(1): Getting a book by index from a shelf
  • O(n): Checking all items in a shopping list
  • O(log n): Binary search in a sorted phone book
Space Complexity

Definition: Space complexity is a measure of the total memory used by an algorithm relative to input size.

Why It Matters: Crucial in memory-limited environments and large-scale systems.

Components:

  • Input space: Memory for input values
  • Auxiliary space: Temporary space used during execution

Examples:

  • Bubble Sort – O(1) space (in-place)
  • Merge Sort – O(n) space (extra array)
  • Quick Sort – O(log n) space (recursive stack)
  • Fibonacci with memoization – O(n) space

Tip: In-place algorithms (like Quick Sort) are memory efficient.

Time vs Space Trade-off

Sometimes improving time complexity increases space usage and vice versa.

  • Hashing: Fast lookups (O(1)) but uses extra memory
  • Memoization: Faster recursion with more space usage
Bubble Sort

Idea: Repeatedly swap adjacent elements if they are in the wrong order.

Time Complexity: O(n²)

void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
Selection Sort

Idea: Find the smallest element and place it at the beginning.

Time Complexity: O(n²)

void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) { minIdx = j; } } int temp = arr[minIdx]; arr[minIdx] = arr[i]; arr[i] = temp; } }
Merge Sort

Idea: Divide the array into halves, sort and merge them recursively.

Time Complexity: O(n log n)

void merge(int[] arr, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int[] L = new int[n1]; int[] R = new int[n2]; for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++]; } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; } void mergeSort(int[] arr, int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } }
Linear Search

Idea: Traverse the array and compare each element to the target.

Time Complexity: O(n)

Use Case: Unsorted arrays, small datasets

int linearSearch(int[] arr, int key) { for (int i = 0; i < arr.length; i++) { if (arr[i] == key) return i; } return -1; }
Binary Search

Idea: Divide the sorted array in half and compare mid with the key.

Time Complexity: O(log n)

Use Case: Sorted arrays

int binarySearch(int[] arr, int key) { int low = 0, high = arr.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == key) return mid; else if (arr[mid] < key) low = mid + 1; else high = mid - 1; } return -1; }
1. LeetCode #1: Two Sum

Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
2. LeetCode #26: Remove Duplicates from Sorted Array

Problem: Given a sorted array nums, remove the duplicates in-place such that each element appears only once and return the new length.

Example:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
3. LeetCode #53: Maximum Subarray

Problem: Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6 (subarray: [4,-1,2,1])
4. LeetCode #1346: Check If N and Its Double Exist

Problem: Given an array arr, check if there exists two indices i and j such that i != j and arr[i] == 2 * arr[j].

Example:

Input: arr = [10,2,5,3]
Output: true
5. LeetCode #1470: Shuffle the Array

Problem: Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn], return the array in the form [x1,y1,x2,y2,...,xn,yn].

Example:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7]
6. LeetCode #1365: How Many Numbers Are Smaller Than the Current Number

Problem: For each number in the array nums, count how many numbers are smaller than it and return the result as an array.

Example:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
7. LeetCode #1480: Running Sum of 1d Array

Problem: Return the running sum of the given array. The running sum is defined as: runningSum[i] = sum(nums[0]...nums[i]).

Example:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
8. LeetCode #1672: Richest Customer Wealth

Problem: Given a 2D array accounts where accounts[i][j] is the amount of money the i-th customer has in the j-th bank, return the wealth that the richest customer has.

Example:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6