Before we dive into the core topics of searching, sorting arrays, and various algorithms, let’s first understand the basics of a few key concepts.
Here, we will cover the very basics of these topics in a simple way. Detailed explanations will follow later. The reason for separating them like this is straightforward: all these topics are interconnected.
If you want to perform searching or sorting, you need to understand arrays, ArrayLists, strings, and how they work. At the same time, if we take just one topic, like arrays, and dive deep into it, we need to know what strings are and when to use ArrayLists.
So, let’s first cover the basics of these concepts, and then we will dive deep into all of them.
Arrays
Arrays are one of the most fundamental data structures in programming.
Imagine you have hundreds of students whose marks you need to store. You can't create 100 variables—well, you could, but it's not the right way. This is where arrays come in. Arrays allow you to store multiple values in a single variable, instead of declaring separate variables for each value. They are especially useful when you need to work with a collection of related data.
1. What is an Array?
In Java, an array is a data structure that can hold multiple values of the same type. Arrays are indexed, with the first element being at index 0, the second at index 1, and so on. Arrays provide a convenient way to manage large amounts of data, such as lists of numbers, strings, or objects, efficiently.
Key Features of Arrays:
Fixed size: Once you declare an array, its size cannot be changed.
Index-based: You can access any element in an array using its index.
Homogeneous: All elements in an array must be of the same data type (e.g., all integers, all strings, etc.).
2. How to Declare and Initialize Arrays in Java
Declaring an Array:
To declare an array in Java, you need to specify the type of elements it will store and use square brackets [].
// Syntax: type[] arrayName;
int[] numbers; // Declares an integer array
String[] names; // Declares a String array
Initializing an Array:
You can initialize an array in two ways: at the time of declaration or later.
1. Using the new keyword:
When you use the new keyword, you create an array with a fixed size, but without initializing the elements.
int[] numbers = new int[5]; // Array of 5 integers, default values are 0
String[] names = new String[3]; // Array of 3 Strings, default values are null
2. Using an initializer list:
You can initialize an array at the time of declaration by providing the elements in curly braces {}.
int[] numbers = {1, 2, 3, 4, 5}; // Array with 5 integers
String[] names = {"Alice", "Bob", "Charlie"}; // Array with 3 Strings
// To initialize an array with values dynamically
int[] numbers = new int[5];
Scanner scanner = new Scanner(System.in);
for (int i = 0; i < numbers.length; i++) {
System.out.print("Enter a number: ");
numbers[i] = scanner.nextInt();
}
3. Accessing Array Elements
You access elements in an array using their index. Remember, Java arrays are zero-indexed, meaning the first element is at index 0.
int[] numbers = {1, 2, 3, 4, 5};
System.out.println(numbers[0]); // Outputs: 1
System.out.println(numbers[2]); // Outputs: 3
//You can also update the value of an element by specifying its index.
numbers[0] = 10; // Updates the first element to 10
System.out.println(numbers[0]); // Outputs: 10
4. Array Length
In Java, the length of an array is stored in a special field called length. This is not a method but a field, so it is accessed without parentheses.
int[] numbers = {1, 2, 3, 4, 5};
System.out.println(numbers.length); // Outputs: 5
5. Multi-Dimensional Arrays
Java supports multi-dimensional arrays, meaning arrays of arrays. A common example is a two-dimensional array, often used to represent matrices or tables.
// Declaring a 2D Array:
int[][] matrix = new int[3][3]; // A 3x3 matrix
// You can initialize a 2D array similarly to a one-dimensional array:
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// Accessing Elements in a 2D Array:
System.out.println(matrix[0][0]); // Outputs: 1
System.out.println(matrix[2][1]); // Outputs: 8
6. Common Array Operations
Java provides several built-in methods and techniques to manipulate arrays. Here are some of the most common operations:
1. Iterating Over Arrays
You can loop through arrays using for loops or enhanced for loops (also called "foreach" loops).
Standard for Loop:
int[] numbers = {1, 2, 3, 4, 5};
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}
// Enhanced for Loop:
for (int number : numbers) {
System.out.println(number);
}
2. Copying Arrays
You can copy arrays in Java using System.arraycopy(), Arrays.copyOf(), or by manually iterating over the elements.
int[] numbers = {1, 2, 3};
int[] copiedNumbers = Arrays.copyOf(numbers, numbers.length);
3. Sorting Arrays
Java provides the Arrays.sort() method to sort arrays in ascending order.
int[] numbers = {5, 3, 8, 1};
Arrays.sort(numbers); // Sorts the array in ascending order
System.out.println(Arrays.toString(numbers)); // Outputs: [1, 3, 5, 8]
4. Searching Arrays
The Arrays.binarySearch() method allows you to search for an element in a sorted array.
int[] numbers = {1, 3, 5, 7, 9};
int index = Arrays.binarySearch(numbers, 5); // Returns index 2
System.out.println(index); // Outputs: 2
Common Problems on Arrays
Find the Maximum and Minimum Element in an Array
// Initialize variables to hold the maximum and minimum values in the array int max = arr[0]; // Assume the first element is the maximum initially int min = arr[0]; // Assume the first element is the minimum initially // Iterate through the array starting from the second element for (int i = 1; i < arr.length; i++) { // Check if the current element is greater than the current maximum if (arr[i] > max) { max = arr[i]; // Update the maximum value } // Check if the current element is smaller than the current minimum if (arr[i] < min) { min = arr[i]; // Update the minimum value } } // Time Complexity: O(n) // The loop runs once for each element in the array, making it linear in terms of the array size.Reverse an Array
// Iterate through the array from both ends towards the center // 'i' starts from the beginning of the array // 'j' starts from the end of the array for (int i = 0, j = arr.length - 1; i < j; i++, j--) { // Swap the elements at index 'i' and 'j' int temp = arr[i]; // Store the value at index 'i' in a temporary variable arr[i] = arr[j]; // Assign the value at index 'j' to index 'i' arr[j] = temp; // Assign the value in the temporary variable to index 'j' } // Time Complexity: O(n) // The loop runs for half the number of elements in the array since two elements are processed in each iteration. // This still results in a linear time complexity as the total number of operations is proportional to the array size.Move All Zeros to the End
// Initialize an index variable to track the position for non-zero elements int index = 0; // Iterate through each element in the array using a for-each loop for (int num : arr) { // If the current element is not zero, place it at the 'index' position if (num != 0) { arr[index++] = num; // Assign the non-zero element to the current index and increment the index } } // After placing all non-zero elements, fill the remaining positions in the array with zeros while (index < arr.length) { arr[index++] = 0; // Assign zero to the current index and increment the index } // Time Complexity: O(n) // The array is traversed twice: once to process non-zero elements and once to fill the rest with zeros. // This results in linear time complexity, proportional to the size of the array.Find the Second Largest Element
// Initialize variables to store the maximum and second maximum values int max = Integer.MIN_VALUE; // Initially set the maximum to the smallest possible integer value int secondMax = Integer.MIN_VALUE; // Initially set the second maximum to the smallest possible integer value // Iterate through each element in the array using a for-each loop for (int num : arr) { // If the current number is greater than the current maximum if (num > max) { secondMax = max; // Update the second maximum to the current maximum max = num; // Update the maximum to the current number } // If the current number is greater than the second maximum but not equal to the maximum else if (num > secondMax && num != max) { secondMax = num; // Update the second maximum to the current number } } // Time Complexity: O(n) // The array is traversed once, making the time complexity linear, proportional to the size of the array.Find All Pairs with a Given Sum
// Define the target sum to find pairs that add up to this value int target = 10; // Iterate through the array using a nested loop to check all pairs for (int i = 0; i < arr.length; i++) { // Inner loop starts from the next element after 'i' for (int j = i + 1; j < arr.length; j++) { // Check if the sum of the pair equals the target if (arr[i] + arr[j] == target) { // Print the pair that adds up to the target System.out.println(arr[i] + ", " + arr[j]); } } } // Time Complexity: O(n^2) // The outer loop runs 'n' times, and for each iteration, the inner loop runs approximately 'n-1' times. // This results in a quadratic time complexity, proportional to the square of the array size.Sum of array elements
class Solution { // Method to calculate the sum of elements in an array public int sum(int arr[], int n) { // Initialize a variable to store the cumulative sum int sum = 0; // Iterate through the array using a for loop for (int i = 0; i < n; i++) { // Add the current element to the cumulative sum sum = sum + arr[i]; } // Return the total sum after the loop completes return sum; } } // This method efficiently calculates the sum of all elements in the array with a time complexity of O(n), // as it traverses the array only once.Count of odd numbers in array
class Solution { // Method to count the number of odd numbers in an array public int countOdd(int[] arr, int n) { // Initialize a variable to store the count of odd numbers int odds = 0; // Iterate through the array using a for loop for (int i = 0; i < n; i++) { // Check if the current element is odd if (arr[i] % 2 != 0) { odds++; // Increment the count of odd numbers } } // Return the total count of odd numbers return odds; } } // Time Complexity: O(n^2) // As each element is checked exactly once.Check if the array is sorted
Advantages:
Efficient access: Arrays allow quick access to elements by index, making it efficient for looking up values.
Fixed size: Arrays have a predefined size, which can be advantageous for memory management in situations where the number of elements is known in advance.
Memory efficient: In comparison to strings (especially immutable strings), arrays can be more memory-efficient when working with a collection of items that need to be modified frequently.
Disadvantages:
Fixed size (in some languages): Many languages require arrays to have a fixed size, which can be restrictive if the size of the array is unknown at compile time.
Homogeneous data: Arrays generally store elements of the same type, limiting flexibility when dealing with mixed data types.
Limited functionality: Basic arrays don't offer as many built-in helper methods as strings or more advanced data structures like lists.
When to use Arrays:
When you need to store multiple items of the same type (e.g., numbers, strings, objects).
When the number of elements is known in advance or can be fixed.
When you need fast, random access to data via an index.
When you need to perform repetitive operations on collections of data (like sorting, searching).
Strings
Strings are one of the most frequently used data structures in programming.
Let’s begin with the fundamentals and gradually dive into more advanced concepts.
1. What is a String in Java?
In Java, a String is a sequence of characters. It is one of the most commonly used data types for text manipulation. Strings are immutable in Java, which means once a string is created, its value cannot be changed. Instead, any operation that modifies a string creates a new string.
Key Features of Strings:
Immutable: Once a string is created, its value cannot be changed.
Index-based: You can access each character in a string by its index. The first character is at index 0.
Varied length: Strings can vary in length and can hold any number of characters, including special characters, spaces, and punctuation marks.
2. Declaring and Initializing Strings in Java
Declaring a String:
In Java, you declare a string by specifying the String type.
public class StringExample {
public static void main(String[] args) {
// Declaring and initializing a String
String greeting = "Hello, World!";
// Printing the String to the console
System.out.println(greeting);
}
}
Initializing a String:
You can initialize a string in several ways:
- Using string literals:
String message = "Hello, World!"; // String initialized with a literal
- Using the
newkeyword:
String message = new String("Hello, World!"); // Creates a new String object
3. Common String Operations
Here are some common string methods. Let's understand them before we move on to the questions.
// Demonstrating String operations in Java
public class Main {
public static void main(String[] args) {
// Declare a String variable
String greeting = "Hello, World!";
// Display the String
System.out.println(greeting);
// String operations
// 1. Accessing characters in a String
char firstCharacter = greeting.charAt(0); // Get the first character
char fifthCharacter = greeting.charAt(4); // Get the fifth character
System.out.println("First character: " + firstCharacter);
System.out.println("Fifth character: " + fifthCharacter);
// 2. Concatenating Strings
String name = "Java";
String fullGreeting = greeting + " Welcome to " + name + " programming!";
System.out.println("Concatenated String: " + fullGreeting);
// Alternatively, using concat() method
String additionalText = " Have fun coding!";
String concatenatedMessage = fullGreeting.concat(additionalText);
System.out.println("Concatenated using concat(): " + concatenatedMessage);
// 3. Find the length of the String
int length = greeting.length();
System.out.println("Length of the String: " + length);
// 4. Convert the String to uppercase
String uppercaseGreeting = greeting.toUpperCase();
System.out.println("Uppercase: " + uppercaseGreeting);
// 5. Replace a word in the String
String replacedGreeting = greeting.replace("World", "Java");
System.out.println("Replaced String: " + replacedGreeting);
// 6. Extract a substring
String substring = greeting.substring(7, 12); // "World"
System.out.println("Substring: " + substring);
// 7. Check if the String contains a specific word
boolean containsHello = greeting.contains("Hello");
System.out.println("Contains 'Hello': " + containsHello);
// 7. Removing extra spaces
String message = " Hello ";
System.out.println(message.trim()); // Outputs: Hello
}
}
4. String Questions
1 Reverse a String:
Reversing a string involves swapping characters from both ends towards the centre.
// Demonstrating how to reverse a String in Java
public class Main {
public static void main(String[] args) {
// Declare and initialize a String variable
String original = "Hello, World!";
// 1. Reverse a String using a loop
String reversedUsingLoop = reverseStringUsingLoop(original);
System.out.println("Reversed String (using loop): " + reversedUsingLoop);
// 2. Reverse a String using StringBuilder
String reversedUsingStringBuilder = reverseStringUsingStringBuilder(original);
System.out.println("Reversed String (using StringBuilder): " + reversedUsingStringBuilder);
}
/**
* Method to reverse a string using a loop
* @param str the original string
* @return the reversed string
*/
public static String reverseStringUsingLoop(String str) {
StringBuilder reversed = new StringBuilder(); // To store the reversed string
for (int i = str.length() - 1; i >= 0; i--) { // Loop from the end of the string
reversed.append(str.charAt(i)); // Append each character to the result
}
return reversed.toString(); // Convert StringBuilder to String and return
}
/**
* Method to reverse a string using StringBuilder's reverse() method
* @param str the original string
* @return the reversed string
*/
public static String reverseStringUsingStringBuilder(String str) {
StringBuilder sb = new StringBuilder(str); // Initialize StringBuilder with the string
return sb.reverse().toString(); // Reverse and convert to String
}
}
2 Palindrome Check:
A palindrome is a word that reads the same backward as forward. To check if a string is a palindrome:
// Demonstrating how to check if a String is a palindrome in Java
public class Main {
public static void main(String[] args) {
// Declare and initialize a String variable
String input = "madam"; // Change this value to test different strings
// 1. Palindrome check using a loop
boolean isPalindromeUsingLoop = checkPalindromeUsingLoop(input);
System.out.println("Is Palindrome (using loop): " + isPalindromeUsingLoop);
// 2. Palindrome check using StringBuilder
boolean isPalindromeUsingStringBuilder = checkPalindromeUsingStringBuilder(input);
System.out.println("Is Palindrome (using StringBuilder): " + isPalindromeUsingStringBuilder);
}
/**
* Method to check if a string is a palindrome using a loop
* @param str the input string
* @return true if the string is a palindrome, false otherwise
*/
public static boolean checkPalindromeUsingLoop(String str) {
int start = 0; // Pointer at the beginning of the string
int end = str.length() - 1; // Pointer at the end of the string
while (start < end) { // Loop until the pointers meet
if (str.charAt(start) != str.charAt(end)) {
return false; // Return false if characters don't match
}
start++;
end--;
}
return true; // Return true if the loop completes without mismatch
}
/**
* Method to check if a string is a palindrome using StringBuilder
* @param str the input string
* @return true if the string is a palindrome, false otherwise
*/
public static boolean checkPalindromeUsingStringBuilder(String str) {
StringBuilder sb = new StringBuilder(str); // Initialize StringBuilder with the input string
String reversed = sb.reverse().toString(); // Reverse the string and convert to String
return str.equals(reversed); // Compare original and reversed strings
}
}
3 Largest Odd Number in a String:
To find the largest odd number in a string, you need to extract all numbers and check if they are odd.
// Demonstrating how to find the largest odd number in a string in Java
public class Main {
public static void main(String[] args) {
// Declare and initialize a String containing digits
String input = "57483902"; // Change this value to test different strings
// 1. Find the largest odd number using a loop
String largestOddUsingLoop = findLargestOddNumberUsingLoop(input);
System.out.println("Largest Odd Number (using loop): " + largestOddUsingLoop);
// 2. Find the largest odd number using String manipulation
String largestOddUsingStringManipulation = findLargestOddNumberUsingStringManipulation(input);
System.out.println("Largest Odd Number (using String manipulation): " + largestOddUsingStringManipulation);
}
/**
* Method to find the largest odd number using a loop
* @param str the input string
* @return the largest odd number as a string, or an empty string if none exists
*/
public static String findLargestOddNumberUsingLoop(String str) {
// Loop from the last character to the first
for (int i = str.length() - 1; i >= 0; i--) {
char currentChar = str.charAt(i); // Get the current character
int digit = Character.getNumericValue(currentChar); // Convert it to an integer
// Check if the digit is odd
if (digit % 2 != 0) {
// Return the substring from the beginning to this character (inclusive)
return str.substring(0, i + 1);
}
}
// Return an empty string if no odd number is found
return "";
}
/**
* Method to find the largest odd number using String manipulation
* @param str the input string
* @return the largest odd number as a string, or an empty string if none exists
*/
public static String findLargestOddNumberUsingStringManipulation(String str) {
int lastOddIndex = -1; // To store the index of the last odd digit
// Loop through the string to find the last odd digit
for (int i = 0; i < str.length(); i++) {
char currentChar = str.charAt(i); // Get the current character
int digit = Character.getNumericValue(currentChar); // Convert it to an integer
if (digit % 2 != 0) { // Check if the digit is odd
lastOddIndex = i; // Update the last odd index
}
}
// If an odd digit was found, return the substring up to the last odd index
return lastOddIndex != -1 ? str.substring(0, lastOddIndex + 1) : "";
}
}
4 Longest Common Prefix:
To find the longest common prefix in an array of strings, you can compare characters at each index.
// Demonstrating how to find the longest common prefix in Java
public class Main {
public static void main(String[] args) {
// Declare and initialize an array of strings
String[] words = {"flower", "flow", "flight"}; // Change this array to test different inputs
// Find the longest common prefix
String longestCommonPrefix = findLongestCommonPrefix(words);
System.out.println("Longest Common Prefix: " + longestCommonPrefix);
}
/**
* Method to find the longest common prefix among an array of strings
* @param strs the array of strings
* @return the longest common prefix as a string, or an empty string if no common prefix exists
*/
public static String findLongestCommonPrefix(String[] strs) {
// Return an empty string if the input array is null or empty
if (strs == null || strs.length == 0) {
return "";
}
// Start with the first string as the initial prefix
String prefix = strs[0];
// Iterate through the remaining strings in the array
for (int i = 1; i < strs.length; i++) {
// Compare the current prefix with each string
while (strs[i].indexOf(prefix) != 0) {
// Shorten the prefix by removing the last character
prefix = prefix.substring(0, prefix.length() - 1);
// If the prefix becomes empty, return an empty string
if (prefix.isEmpty()) {
return "";
}
}
}
return prefix; // Return the final common prefix
}
}
5 Rotate String:
To rotate a string by a given number of positions, you can split the string at the rotation index and concatenate the parts.
// Demonstrating how to rotate a string in Java
public class Main {
public static void main(String[] args) {
// Example input string and rotation value
String input = "abcdef"; // The string to rotate
int rotation = 2; // Number of positions to rotate
// Perform the rotation
String rotatedString = rotateString(input, rotation);
System.out.println("Rotated String: " + rotatedString);
}
/**
* Method to rotate a string by a given number of positions
* @param str the input string
* @param positions the number of positions to rotate
* @return the rotated string
*/
public static String rotateString(String str, int positions) {
// Handle edge cases
if (str == null || str.isEmpty()) {
return str; // Return as-is if the string is null or empty
}
// Ensure the rotation value is within the string's length
int length = str.length();
positions = positions % length; // Reduce positions if greater than the string length
// If no rotation is needed, return the original string
if (positions == 0) {
return str;
}
// Split the string into two parts: (length - positions) and positions
String part1 = str.substring(0, length - positions); // Characters from the start
String part2 = str.substring(length - positions); // Characters to rotate to the front
// Concatenate the two parts to form the rotated string
return part2 + part1;
}
}
7 anagrams - Two strings are anagrams if they have the same characters in the same frequency. You can check this by sorting both strings and comparing them.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// Example input strings
String str1 = "listen"; // Change these values to test different cases
String str2 = "silent";
// Check if the strings are anagrams
boolean areAnagrams = checkAnagrams(str1, str2);
System.out.println("Are the strings anagrams? " + areAnagrams);
}
/**
* Method to check if two strings are anagrams
* @param s1 the first string
* @param s2 the second string
* @return true if the strings are anagrams, false otherwise
*/
public static boolean checkAnagrams(String s1, String s2) {
// Edge case: If lengths differ, they cannot be anagrams
if (s1.length() != s2.length()) {
return false;
}
// Convert both strings to character arrays
char[] charArray1 = s1.toCharArray();
char[] charArray2 = s2.toCharArray();
// Sort the character arrays
Arrays.sort(charArray1);
Arrays.sort(charArray2);
// Compare the sorted arrays
return Arrays.equals(charArray1, charArray2);
}
}
8 Sort Characters by Frequency:
To sort characters in a string by frequency, you can use a frequency map and a priority queue.
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
(a, b) -> b.getValue() - a.getValue());
pq.addAll(map.entrySet());
StringBuilder result = new StringBuilder();
while (!pq.isEmpty()) {
Map.Entry<Character, Integer> entry = pq.poll();
for (int i = 0; i < entry.getValue(); i++) {
result.append(entry.getKey());
}
}
return result.toString();
}
Advantages:
Immutability: In many programming languages, strings are immutable, meaning their value cannot be changed once created. This helps in preventing accidental changes.
Easy to use: Strings are built-in data types in most languages and come with many helper functions (like concatenation, search, split) that make string manipulation easier.
Readable: String data is often more human-readable, as it represents textual information directly.
Disadvantages:
Fixed length: In some languages, strings may have a fixed length, making operations like resizing or inserting characters more challenging.
Memory inefficient for large data: Since strings are immutable, any modification creates a new string, which can be less memory-efficient when working with large text data.
Limited operations: For complex data manipulation, strings may not be the best choice (e.g., numeric computations, complex transformations).
When to use Strings:
When you need to work with textual data (e.g., names, descriptions, messages).
When you need to manipulate, format, or analyze text.
When the size of the data is not likely to change significantly.
Hashing
Hashing is a way to turn large data into smaller, fixed-size values using a hash function. These values are kept in a hash table, which makes it easy to quickly find data using the hash code.
Hash Functions
A hash function takes input data (keys) and produces a hash code, an integer that serves as an index in the hash table. The efficiency of hashing depends on the quality of the hash function. In Java, commonly used hash functions include:
Object.hashCode(): Every Java object has a
hashCode()method that returns an integer hash code.Custom Hash Functions: Developers can define their own hash functions tailored to specific requirements.
We don't need to dive deep into this right now, especially regarding DSA itself, but we will cover it when we need to create a custom one.
Hashing Data Structures in Java
HashMap: Stores key-value pairs and allows for efficient retrieval, insertion, and deletion.
HashSet: Implements the Set interface using a hash table and ensures no duplicate elements.
LinkedHashMap: Maintains insertion order while leveraging a hash table.
Hashtable: Similar to
HashMapbut synchronized and thread-safe.
Again, we will deep dive into this later.
Lets see the example of how it looks
// HashMap: Declaration
import java.util.HashMap;
public class HashMapExample {
public static void main(String[] args) {
// Declare a HashMap to store names (key) and their ages (value)
HashMap<String, Integer> ageMap = new HashMap<>();
// Add key-value pairs to the HashMap
ageMap.put("Alice", 25);
ageMap.put("Bob", 30);
ageMap.put("Charlie", 22);
// Access and print a value using a key
System.out.println("Age of Bob: " + ageMap.get("Bob")); // Output: Age of Bob: 30
// Iterate through the HashMap and print all key-value pairs
for (String key : ageMap.keySet()) {
System.out.println(key + " is " + ageMap.get(key) + " years old.");
}
}
}
// Output
// Age of Bob: 30
// Alice is 25 years old.
// Bob is 30 years old.
// Charlie is 22 years old.
// HashSet: Declaration
import java.util.HashSet;
public class HashSetExample {
public static void main(String[] args) {
// Declare a HashSet to store unique numbers
HashSet<Integer> numberSet = new HashSet<>();
// Add elements to the HashSet
numberSet.add(10);
numberSet.add(20);
numberSet.add(30);
numberSet.add(10); // Duplicate, won't be added
// Check if an element exists in the HashSet
System.out.println("Contains 20? " + numberSet.contains(20)); // Output: Contains 20? true
// Iterate through the HashSet and print all elements
System.out.println("HashSet elements:");
for (int num : numberSet) {
System.out.println(num);
}
}
}
// Output
// Contains 20? true
// HashSet elements:
// 10
// 20
// 30
import java.util.HashSet;
// Class to check if an array contains duplicates
public class ContainsDuplicate {
/**
* Method to determine if an array contains duplicates.
* @param nums The array of integers to check.
* @return true if duplicates are found, otherwise false.
*/
public static boolean hasDuplicate(int[] nums) {
// Create a HashSet to store unique elements from the array
HashSet<Integer> set = new HashSet<>();
// Iterate through each element in the array
for (int num : nums) {
// Attempt to add the current number to the HashSet
// If add() returns false, it means the number is already in the set
if (!set.add(num)) {
return true; // Duplicate found, return true
}
}
// If the loop completes without finding duplicates, return false
return false;
}
// Main method to test the hasDuplicate function
public static void main(String[] args) {
// Define a sample array to check for duplicates
int[] nums = {1, 2, 3, 4, 5, 1};
// Call the hasDuplicate method and print the result
System.out.println(hasDuplicate(nums)); // Output: true
}
}
import java.util.HashMap;
// Class to count and display frequencies of elements in an array
public class FrequencyCounter {
/**
* Method to count and print the frequencies of elements in an array.
* @param nums The array of integers whose frequencies are to be counted.
*/
public static void countFrequencies(int[] nums) {
// Create a HashMap to store each number as a key and its frequency as the value
HashMap<Integer, Integer> frequencyMap = new HashMap<>();
// Iterate through the array
for (int num : nums) {
// Update the frequency of the current number in the HashMap
// If the number is already in the map, increment its value by 1
// If not, add it with an initial frequency of 1
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
// Iterate through the keys of the HashMap to display the frequencies
for (int key : frequencyMap.keySet()) {
// Print each key (number) and its associated frequency
System.out.println(key + ": " + frequencyMap.get(key));
}
}
// Main method to test the countFrequencies function
public static void main(String[] args) {
// Define a sample array to count frequencies
int[] nums = {1, 2, 2, 3, 3, 3};
// Call the countFrequencies method with the sample array
countFrequencies(nums);
// Output:
// 1: 1
// 2: 2
// 3: 3
}
}
import java.util.HashSet;
// Class to find the intersection of two arrays
public class ArrayIntersection {
/**
* Method to find the intersection of two arrays.
* @param nums1 The first array of integers.
* @param nums2 The second array of integers.
* @return An array containing the unique elements that are present in both arrays.
*/
public static int[] intersection(int[] nums1, int[] nums2) {
// HashSet to store unique elements from the first array
HashSet<Integer> set1 = new HashSet<>();
// HashSet to store the intersection of the two arrays
HashSet<Integer> resultSet = new HashSet<>();
// Add all elements from the first array to set1
for (int num : nums1) {
set1.add(num);
}
// Check each element in the second array
// If it exists in set1, add it to resultSet
for (int num : nums2) {
if (set1.contains(num)) {
resultSet.add(num);
}
}
// Convert the resultSet to an array
int[] result = new int[resultSet.size()];
int index = 0;
for (int num : resultSet) {
result[index++] = num; // Add each element to the result array
}
// Return the resulting intersection array
return result;
}
// Main method to test the intersection function
public static void main(String[] args) {
// Define two sample arrays
int[] nums1 = {1, 2, 2, 3};
int[] nums2 = {2, 2, 3, 4};
// Call the intersection method and store the result
int[] intersection = intersection(nums1, nums2);
// Print the elements of the intersection array
for (int num : intersection) {
System.out.print(num + " "); // Output: 2 3
}
}
}
// Demonstrating how to check if two strings are isomorphic in Java
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
// Example input strings
String s1 = "egg"; // Change these values to test different cases
String s2 = "add";
// Check if the strings are isomorphic
boolean isIsomorphic = areIsomorphic(s1, s2);
System.out.println("Are the strings isomorphic? " + isIsomorphic);
}
/**
* Method to check if two strings are isomorphic
* @param s1 the first string
* @param s2 the second string
* @return true if the strings are isomorphic, false otherwise
*/
public static boolean areIsomorphic(String s1, String s2) {
// If the lengths are different, they cannot be isomorphic
if (s1.length() != s2.length()) {
return false;
}
// HashMap to store character mappings from s1 to s2
HashMap<Character, Character> mapS1ToS2 = new HashMap<>();
// HashMap to store character mappings from s2 to s1
HashMap<Character, Character> mapS2ToS1 = new HashMap<>();
// Iterate through the characters of both strings
for (int i = 0; i < s1.length(); i++) {
char charS1 = s1.charAt(i); // Character from s1
char charS2 = s2.charAt(i); // Corresponding character from s2
// Check if there is already a mapping for charS1 in mapS1ToS2
if (mapS1ToS2.containsKey(charS1)) {
// If the mapping doesn't match charS2, return false
if (mapS1ToS2.get(charS1) != charS2) {
return false;
}
} else {
// Add a new mapping from charS1 to charS2
mapS1ToS2.put(charS1, charS2);
}
// Check if there is already a mapping for charS2 in mapS2ToS1
if (mapS2ToS1.containsKey(charS2)) {
// If the mapping doesn't match charS1, return false
if (mapS2ToS1.get(charS2) != charS1) {
return false;
}
} else {
// Add a new mapping from charS2 to charS1
mapS2ToS1.put(charS2, charS1);
}
}
// If all characters map correctly, the strings are isomorphic
return true;
}
}
Common Methods in Hashing
HashMap Methods:
put(K key, V value): Inserts a key-value pair.get(Object key): Retrieves the value associated with the key.remove(Object key): Removes the key-value pair.containsKey(Object key): Checks if a key exists.containsValue(Object value): Checks if a value exists.
HashSet Methods:
add(E element): Adds an element to the set.remove(Object o): Removes the specified element.contains(Object o): Checks if the set contains the specified element.
Time Complexity of Hashing Operations
| Operation | Average Case | Worst Case |
| Search | O(1) | O(n) |
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |
Average Case: Most operations take constant time due to efficient hash functions.
Worst Case: Occurs when there are too many collisions, leading to a linear time complexity.
Advantages of Hashing
Fast Access: Provides O(1) average-time complexity for search, insert, and delete operations.
Efficient Memory Usage: Compact storage for data.
Flexibility: Supports dynamic resizing and custom hash functions.
Disadvantages of Hashing
Collisions: When two keys produce the same hash code, it can lead to performance degradation.
Memory Overhead: Large hash tables may require significant memory.
Complex Implementation: Designing an efficient hash function can be challenging.
Collision Handling Techniques
Chaining: Uses a linked list to store all elements that hash to the same index.
Open Addressing:
Linear Probing: Places the item in the next available slot.
Quadratic Probing: Uses a quadratic function to find the next slot.
Double Hashing: Uses a second hash function to determine the probe sequence.
When to Use Hashing
Fast Data Retrieval: Ideal for scenarios requiring quick lookups, such as caching.
Unique Key Management: Ensures unique keys in data storage.
Dynamic Data Storage: Works well with datasets that grow dynamically.
Why Use Hashing?
Hashing is indispensable for applications requiring rapid data access and efficient management of large datasets. It powers systems such as:
Databases: Indexing for fast queries.
Compilers: Symbol tables for variable lookups.
Web Applications: Caching and session management.
In this blog, we've covered the key concepts of arrays, strings, and hashing in Java, providing you with a solid foundation to tackle DSA problems effectively. By mastering these topics, we can now progress to more detailed sections on problem-solving and learning DSA.