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
LeetCode #125: Valid Palindrome

Problem: Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example:

Input: "A man, a plan, a canal: Panama"
Output: true
LeetCode #344: Reverse String

Problem: Write a function that reverses a string. The input string is given as a char array s. Do it in-place.

Example:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
LeetCode #387: First Unique Character in a String

Problem: Given a string s, find the first non-repeating character and return its index. If it doesn't exist, return -1.

Example:

Input: "leetcode"
Output: 0
LeetCode #28: Find the Index of the First Occurrence in a String

Problem: Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example:

Input: haystack = "hello", needle = "ll"
Output: 2
LeetCode #349: Intersection of Two Arrays

Problem: Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique, and you may return the result in any order.

Example:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]