This repository contains solutions to various algorithmic problems, organized by data structure categories. Each solution is implemented in Java and includes detailed comments explaining the approach.
- Purpose: Practice and demonstrate problem-solving skills using various data structures and algorithms
- Language: Java
- Organization: Solutions are grouped by the primary data structure they utilize
- Documentation: Each solution includes time complexity analysis and approach description
-
Longest Substring Without Repeating Characters (
longestsusbtring.java)- Uses a sliding window approach with a HashSet to find the longest substring without repeating characters
- Time Complexity: O(n)
-
Sentence Similarity (
sentencesimilarity.java)- Determines if two sentences are similar by checking if one is a prefix or suffix of the other
- Time Complexity: O(n)
-
String Multiplication (
stringmultiply.java)- Implements multiplication of two large numbers represented as strings
- Time Complexity: O(m*n)
-
String Reverse (
stringreverse.java)- Reverses a character array in-place using two pointers
- Time Complexity: O(n)
-
First and Last Occurrence (
firstandlastocc.java)- Finds the first and last occurrence of each character in a string using HashMap
- Stores indices as arrays for efficient tracking
- Time Complexity: O(n)
-
Character Occurrence Count (
occurrence.java)- Counts occurrences of each character in a string using array hashing
- Uses character offset technique for efficient counting
- Time Complexity: O(n)
-
String to Integer (ATOI) (
ATOI.java)- Converts string to integer with proper handling of edge cases
- Handles whitespace, signs, and integer overflow/underflow
- Time Complexity: O(n)
-
Pangram Checker (
Main.java)- Checks if a given string contains all letters from 'a' to 'z'
- Uses boolean array for efficient letter tracking
- Time Complexity: O(n)
-
Contains Duplicate II (
containsduplicate2.java)- Checks if an array contains duplicates within a given distance k
- Uses HashMap to track indices
- Time Complexity: O(n)
-
Contains Duplicate III (
containsduplicate3.java)- Checks if an array contains duplicates within a given index difference and value difference
- Time Complexity: O(n)
-
Find Maximum Average (
findmaxaverage.java)- Uses sliding window technique to find the maximum average of a subarray of size k
- Time Complexity: O(n)
-
Four Sum (
foursum.java)- Finds all unique quadruplets in an array that sum up to a target value
- Uses sorting and two pointers technique
- Time Complexity: O(n³)
-
Median of Two Sorted Arrays (
Mediantwoarray.java)- Calculates the median of two sorted arrays by merging them
- Time Complexity: O(m+n)
-
Search in Rotated Sorted Array (
searchinrotatedarray.java)- Uses modified binary search to find a target value in a rotated sorted array
- Time Complexity: O(log n)
-
Three Sum (
ThreeSum.java)- Finds all unique triplets in an array that sum up to zero
- Uses sorting and two pointers technique
- Time Complexity: O(n²)
-
Three Sum Closest (
Threesumclosest.java)- Finds the sum of three integers in an array that is closest to a target value
- Uses sorting and two pointers technique
- Time Complexity: O(n²)
-
Subarray Sum Equals Zero (
SubArrayzero.java)- Checks if there exists a subarray with sum equal to zero
- Uses prefix sum technique with HashSet to detect zero-sum subarrays
- Time Complexity: O(n)
-
Binary Search (
binarysearch.java)- Classic binary search implementation to find a target element in a sorted array
- Uses left and right pointers to divide search space
- Time Complexity: O(log n)
-
Lower Bound (
lowerbounnd.java)- Finds the first position where target can be inserted to maintain sorted order
- Returns index of first element >= target
- Time Complexity: O(log n)
-
Upper Bound (
upperbound.java)- Finds the last position where target can be inserted to maintain sorted order
- Returns index of first element > target
- Time Complexity: O(log n)
-
Merge Intervals (
mergeintervals.java)- Merges overlapping intervals in a 2D array
- Uses sorting by start time
- Time Complexity: O(n log n)
-
Search in a 2D Matrix (
SearchInArrayBS.java)- Uses binary search to efficiently search for a target value in a sorted 2D matrix
- Time Complexity: O(log(m*n))
-
Set Matrix Zeros (
setmatrixzero.java)- Sets entire row and column to zero if any element in that row/column is zero
- Uses boolean arrays to mark rows and columns to be zeroed
- Time Complexity: O(m*n)
-
Matrix Boundary Traversal (
boundaary.java)- Traverses and prints the boundary elements of a 2D matrix
- Time Complexity: O(m+n)
-
Diagonal and Anti-diagonal Sum (
digandantidig.java)- Calculates sum of main diagonal and anti-diagonal elements
- Time Complexity: O(n)
-
Row and Column Sum (
rcsum.java)- Calculates sum of each row and column in a matrix
- Time Complexity: O(m*n)
-
Matrix Addition (
sumofmat.java)- Adds two matrices element by element
- Time Complexity: O(m*n)
-
Matrix Subtraction (
suboftwomat.java)- Subtracts one matrix from another element by element
- Time Complexity: O(m*n)
-
Matrix Min/Max (
minmax.java)- Finds minimum and maximum elements in a 2D matrix
- Time Complexity: O(m*n)
-
Matrix Sorting (
sorting.java)- Sorts elements of a 2D matrix
- Time Complexity: O(mnlog(m*n))
-
Symmetric Matrix Check (
symmetric.java)- Checks if a matrix is symmetric (equal to its transpose)
- Time Complexity: O(n²)
-
Upper and Lower Triangular (
utlt.java)- Separates matrix into upper and lower triangular parts
- Time Complexity: O(n²)
-
Zigzag Pattern Traversal (
zigzagpattern.java)- Traverses matrix in zigzag pattern (alternating left-right and right-left)
- Time Complexity: O(m*n)
-
Stack Implementation (
stack.java)- Array-based stack implementation with push, pop, top, and size operations
- Demonstrates basic stack operations with fixed-size array
- Time Complexity: O(1) for all operations
-
Queue Implementation (
queue.java)- Array-based queue implementation with enqueue, dequeue, front, and rear operations
- Demonstrates basic queue operations with circular array approach
- Time Complexity: O(1) for all operations
-
Balanced Parentheses (
balancedparen.java)- Checks if parentheses, brackets, and braces are balanced in a string
- Uses stack to match opening and closing brackets
- Time Complexity: O(n)
-
Infix to Postfix Conversion (
infixtopostfix.java)- Converts infix expressions to postfix notation using stack
- Handles operator precedence and associativity
- Time Complexity: O(n)
-
Postfix to Infix Conversion (
postfixtoinfix.java)- Converts postfix expressions back to infix notation using stack
- Reconstructs the original expression format
- Time Complexity: O(n)
-
Stack/Queue Utility (
a.java)- Additional utility functions for stack and queue operations
- Provides helper methods for advanced stack/queue manipulations
- Time Complexity: Varies based on operation
- Happy Number (
happynumber.java)- Determines if a number is "happy" using Floyd's Cycle-Finding Algorithm
- Uses fast and slow pointers to detect cycles in the sequence
- Time Complexity: O(log n)
-
ListNode Class (
ListNode.java)- Defines the basic node structure used in linked list implementations
- Contains constructors for creating nodes with different initialization options
- Also includes a RemoveNthFromEnd implementation as an alternative to Removenth.java
- Time Complexity: O(1) for node creation, O(n) for the RemoveNthFromEnd operation
-
Delete Duplicates (
deleteDuplicates.java)- Removes duplicates from a sorted linked list
- Iterates through the list and removes nodes with duplicate values
- Time Complexity: O(n)
-
Has Cycle (
hasCycle.java)- Detects if a cycle exists in a singly-linked list using Floyd's Cycle-Finding Algorithm
- Uses two pointers moving at different speeds to determine if a cycle is present
- Time Complexity: O(n)
-
Detect Cycle (
detectcycle.java)- Not only detects if a cycle exists but also returns the node where the cycle begins
- Uses Floyd's Cycle-Finding Algorithm with two phases
- Time Complexity: O(n)
-
Intersection of Two Linked Lists (
intersectionoftwoll.java)- Finds the intersection node of two singly-linked lists
- Uses two pointers to traverse the lists and find the intersection point
- Time Complexity: O(n + m)
-
Delete the Middle Node (
deleteatmid.java)- Removes the middle node from a linked list
- Uses fast and slow pointer technique to find the middle node
- Time Complexity: O(n)
-
Remove Nth Node From End (
Removenth.java)- Removes the nth node from the end of a linked list
- Uses two pointers with a gap of n nodes to find the target node
- Time Complexity: O(n)
-
Singly Linked List Implementation (
sll.javaandSinglyLinkedList.java)- Complete implementation of a singly linked list with insertion (FIRST, END, MID), deletion (FIRST, END, MID), finding the middle element, length calculation, and traversal operations
- Provides the foundation for other linked list problems
- Interactive menu-driven implementation in
SinglyLinkedList.java - Time Complexity: O(n) for insertion and printing
-
Doubly Linked List Implementation (
Doublylinkedlist.java)- Complete implementation of a doubly linked list with bidirectional traversal
- Features insertion operations at the beginning, end, and at specific positions
- Features deletion operations at the beginning, end, and at specific positions, also the entire list
- Maintains both head and tail pointers for efficient operations at both ends
- Includes methods for traversal in both forward and reverse directions
- Time Complexity: O(1) for insertions, deletion at beginning/end, O(n) for insertions, deletion at specific positions
-
Reverse Linked List (
Reverse.java)
- Reverses an entire linked list in-place
- Uses iterative approach with three pointers (prev, current, next)
- Time Complexity: O(n)
-
Reverse Linked List Between Positions (
ReverseBetweenDemo.java)- Reverses a portion of a linked list between specified positions (left to right)
- Uses iterative approach with pointer manipulation to reverse the sublist in-place
- Handles edge cases with a dummy node
- Time Complexity: O(n)
-
Sort Linked List (
sort.java)- Sorts a linked list using merge sort algorithm
- Uses fast and slow pointers to find the middle of the list for splitting
- Recursively divides the list and merges sorted sublists
- Time Complexity: O(n log n)
-
Reorder Linked List (
REORDER.java)- Reorders a linked list such that L₀ → L₁ → ... → Lₙ₋₁ → Lₙ becomes L₀ → Lₙ → L₁ → Lₙ₋₁ → ...
- Uses fast and slow pointers to find the middle of the list
- Reverses the second half of the list and then merges the two halves
- Time Complexity: O(n)
-
Add Two Numbers (
AddTwoNumbers.java)- Adds two numbers represented by linked lists where each node contains a single digit
- Numbers are stored in reverse order (least significant digit first)
- Handles carry propagation during addition
- Includes helper methods for building and printing linked lists
- Time Complexity: O(max(m,n)) where m and n are the lengths of the two lists
-
Circular Linked List (
Circularll.java)- Implementation of a circular linked list where the last node points back to the first node
- Supports insertion at the beginning and end of the list
- Includes traversal method that handles the circular nature of the list
- Maintains both head and tail pointers for efficient operations
- Time Complexity: O(1) for insertions, O(n) for traversal
-
Rotate Linked List (
Rotate.java)- Rotates a linked list to the right by k places
- Efficiently handles large rotation values by using modulo operation
- Finds the new head and tail positions after rotation
- Reconnects the list to achieve the rotation effect
- Time Complexity: O(n) where n is the length of the list
-
Merge Nodes Between Zeros (
MergeNodes.java)- Merges nodes between zeros in a linked list by summing values between zero nodes
- Creates new nodes with the sum of values between consecutive zeros
- Handles linked lists that start and end with zero
- Time Complexity: O(n)
-
Reverse Nodes in k-Group (
ReverseKnode.java)- Reverses nodes of a linked list k at a time
- If remaining nodes are less than k, they remain unchanged
- Uses helper functions to find kth node and reverse sublists
- Time Complexity: O(n)
-
Generate All Subsets (
subset.java)- Generates all possible subsets of a given array using backtracking
- Handles duplicates by sorting and skipping duplicate elements
- Uses recursive approach with inclusion/exclusion decisions
- Time Complexity: O(2^n)
-
Combination Sum (
Combinationsum.java)- Finds all unique combinations that sum to a target value
- Elements can be used multiple times
- Uses backtracking with recursive exploration
- Time Complexity: O(2^target)
-
Combination Sum II (
CombinationsumII.java)- Finds all unique combinations that sum to a target value
- Each element can be used only once
- Handles duplicates in input array
- Time Complexity: O(2^n)
-
Combination Sum III (
combinationsum3.java)- Finds all combinations of k numbers that sum to n
- Uses digits 1-9 only, each digit used at most once
- Uses backtracking with constraint checking
- Time Complexity: O(C(9,k))
-
Generate Parentheses (
generateparen.java)- Generates all valid combinations of n pairs of parentheses
- Uses backtracking with balance tracking
- Ensures proper opening and closing of parentheses
- Time Complexity: O(4^n/√n) - Catalan number
-
Subset Sum Equal to Target (
subequ.javaandsubequal.java)- Determines if there exists a subset with sum equal to target
- Uses dynamic programming and backtracking approaches
- Time Complexity: O(n*sum) for DP, O(2^n) for backtracking
-
Count Subsequences (
subsequence_num.java)- Counts the number of subsequences that satisfy certain conditions
- Uses recursive approach with memoization
- Time Complexity: O(2^n)
-
Phone Letter Combinations (
phonelettercomb.java)- Generates all possible letter combinations from a phone number
- Uses backtracking to explore all possible combinations
- Time Complexity: O(4^n)
-
Letter Combinations of a Phone Number (
lettercombination.java)- Maps digits to letters and generates all possible combinations
- Uses recursive approach with digit-to-letter mapping
- Time Complexity: O(4^n)
-
Palindrome Partitioning (
PalindromePartitioning.java)- Partitions a string into palindromic substrings
- Uses backtracking with palindrome checking
- Time Complexity: O(2^n)
-
Test Recursion (
test.java)- Test implementation for recursion problems
- Demonstrates basic recursive problem-solving patterns
- Time Complexity: Varies based on implementation
-
Pattern Printing (
test.c)- C program for printing triangular patterns with letters
- Demonstrates nested loop patterns and character manipulation
- Time Complexity: O(n²)
- Event Management System (
Main.java,Event.java,EventType.java,EventTypeBO.java)- Implements a one-to-many relationship between EventType and Event classes
- EventType can contain multiple Events in an ArrayList
- Event contains event details (name, detail, type, organiserName)
- EventTypeBO provides display functionality for formatted output
- Main class handles CSV input parsing and relationship establishment
- Demonstrates proper object-oriented design with encapsulation
- Time Complexity: O(n) for input processing, O(n*m) for display where n=event types, m=events per type
- Contact Management System (
Main.java,Contact.java,Address.java)- Implements a one-to-one relationship between Contact and Address classes
- Contact has exactly one Address associated with it
- Address contains location details (street, city, state, zip)
- Main class handles input and demonstrates the relationship
- Shows proper encapsulation and association principles
- Time Complexity: O(1) for object creation and access
- Sliding Window: Used for finding subarrays or substrings that satisfy certain conditions
- Two Pointers: Efficient technique for processing arrays and linked lists
- Fast & Slow Pointers: Special two-pointer technique for cycle detection and finding middle elements
- Binary Search: Efficient searching in sorted arrays and matrices
- Sorting: Pre-processing technique to simplify problem-solving
- Hash Tables: For O(1) lookups and tracking frequencies or positions
- Array Manipulation: In-place modifications and traversal techniques
- Linked List Manipulation: Operations like insertion, deletion, and traversal
- Merge Sort: Divide and conquer algorithm for efficient sorting
- Floyd's Cycle-Finding Algorithm: For detecting cycles in sequences or linked lists
- Recursion: Self-referential problem-solving technique
- Backtracking: Systematic exploration of solution space with pruning
- Dynamic Programming: Optimizing recursive solutions with memoization
- Matrix Traversal: Various patterns for processing 2D arrays
- Dummy Node Technique: For simplifying edge cases in linked list operations
- Character Hashing: Array-based frequency counting for character problems
- Boundary Marking: Technique for matrix problems to avoid modifying original data
- Modular Arithmetic: For handling large numbers and rotations efficiently
- Stack Operations: LIFO operations for expression evaluation and bracket matching
- Queue Operations: FIFO operations for level-order processing and scheduling
- Prefix Sum: Efficient technique for subarray sum problems
- String Parsing: Handling edge cases in string-to-number conversion
- Pattern Matching: Recursive and iterative approaches for pattern generation
- Cycle Detection: Floyd's algorithm for detecting cycles in sequences
- String Problems: 8 problems covering substring operations, character counting, string manipulation, and conversion
- Array Problems: 9 problems including duplicates detection, sum problems, search algorithms, and subarray operations
- Binary Search Problems: 3 problems covering basic search, lower bound, and upper bound implementations
- 2D Array/Matrix Problems: 13 problems covering various matrix operations and traversal patterns
- Stack and Queue Problems: 6 problems covering basic data structure operations, expression conversion, and bracket matching
- Two Pointer Problems: 1 problem demonstrating cycle detection techniques
- Linked List Problems: 18 comprehensive problems covering all major linked list operations and algorithms
- Recursion and Backtracking Problems: 12 problems exploring combinatorial algorithms, pattern generation, and recursive solutions
- Relationship Problems: 2 problems demonstrating object-oriented design patterns (one-to-many, one-to-one)
Total Problems Solved: 72
Each solution includes its time complexity analysis to demonstrate efficiency considerations. The implementations focus on optimizing for:
- Time efficiency
- Space efficiency
- Edge case handling
- Clean, readable code structure
- Comprehensive problem coverage from basic to advanced levels
This repository demonstrates proficiency in:
- Data Structure Manipulation: Arrays, Strings, Linked Lists, Matrices
- Algorithm Design Patterns: Two Pointers, Sliding Window, Binary Search, Backtracking
- Problem-Solving Approaches: Iterative, Recursive, Dynamic Programming
- Object-Oriented Design: Class relationships, Encapsulation, Association patterns
- Optimization Techniques: Space-time tradeoffs, Early termination, Constraint handling
- Code Quality: Clean implementations, Edge case handling, Comprehensive testing
-
String Problems: 8 problems covering substring operations, character counting, string manipulation, and conversion
-
Array Problems: 9 problems including duplicates detection, sum problems, search algorithms, and subarray operations
-
Binary Search Problems: 3 problems covering basic search, lower bound, and upper bound implementations
-
2D Array/Matrix Problems: 13 problems covering various matrix operations and traversal patterns
-
Stack and Queue Problems: 6 problems covering basic data structure operations, expression conversion, and bracket matching
-
Two Pointer Problems: 1 problem demonstrating cycle detection techniques
-
Linked List Problems: 18 comprehensive problems covering all major linked list operations and algorithms
-
Recursion and Backtracking Problems: 12 problems exploring combinatorial algorithms, pattern generation, and recursive solutions
-
Relationship Problems: 2 problems demonstrating object-oriented design patterns (one-to-many, one-to-one)
🎯 Total Problems Solved: 72 🚀🎉