🎯 GeeksforGeeks 50 Days of DSA Challenge

A professional collection of Java solutions for the GeeksforGeeks 50 Days of DSA challenge. This repository serves as a comprehensive guide for mastering data structures and algorithms through consistent practice and detailed analysis.

---

📖 Table of Contents

• Overview
• Project Structure
• 50-Day Roadmap & Progress
• Detailed Solutions
• Setup & Execution
• Complexity Summary

---

📋 Overview

This repository focuses on:

• Optimized Solutions: Each problem is solved with a focus on time and space efficiency.
• Detailed Explanations: Step-by-step logic to understand the "why" behind the code.
• Categorization: Problems are grouped into core topics like Arrays, Strings, and DP.

---

📂 Project Structure

GeeksforGeeks/
├── Array/        # Solutions for Array-based problems
├── String/       # Solutions for String manipulation
├── DP/           # Dynamic Programming challenges
└── Readme.md     # Project documentation

---

🚀 50-Day Roadmap & Progress

Day	Topic	Problem Name	Solution
1	Array	Second Largest	Day1.java
2	Array	Reverse an Array	Day2.java
3	Array	Move All Zeroes to End	Day3.java
4	Array	Rotate Array	Day4.java
5	Array	Next Permutation	Day5.java
6	Array	Stock Buy and Sell – Max one Transaction	Day6.java
7	Array	Majority Element - More Than n/3	Day7.java
8	Array	Kadane's Algorithm	Day8.java
9	Array	Stock Buy and Sell – Multiple Transaction	Day9.java
10	Array	Maximum Product Subarray	Day10.java
11	Array	Minimize the Heights II	Day11.java
12	Array	Smallest Positive Missing	Day12.java
13	Array	Repetitive Addition of Digits	Day13.java
14	Array	Last Moment Before Ants Fall Out	Day14.java
15	Array	Split Array in Three Equal Sum Subarrays	Day15.java
16	Array	Maximize Number of 1's	Day16.java
17	Array	Max Circular Subarray Sum	Day17.java
18	String	Anagram	Day18.java
19	String	Non Repeating Character	Day19.java
20	String	Search Pattern	Day20.java
21	String	Min Chars to Add for Palindrome	Day21.java
22	String	Fizz Buzz	Day22.java
23	String	Palindrome Sentence	Day23.java
24	String	CamelCase Pattern Matching	Day24.java
25	String	Longest Prefix Suffix	Day25.java
26	String	Add Binary Strings	Day26.java
27	String	Implement Atoi	Day27.java
28	String	Minimum repeat to make substring	Day28.java
29	Array	Min and Max in Array	Day29.java
30	Array	Indexes of Subarray Sum	Day30.java
31	Array	Minimum Jumps	Day31.java
32	Array	Array Leaders	Day32.java
33	Array	Array Duplicates	Day33.java
34	Array	Sort 0s, 1s and 2s	Day34.java
35	Array	Kth Smallest	Day35.java
36	Array	Parenthesis Checker	Day36.java
37	Array	Missing And Repeating	Day37.java
38	Array	Array Search	Day38.java
39	Array	Array Subset	Day39.java
40	Array	Detect Loop in Linked List	Day40.java
41	Array	BFS of graph	Day41.java
42	DP	Number of Valid Parentheses	Day42.java
43	Array	Missing in Array	Day43.java
44	Array	Equilibrium Point	Day44.java
45	Array	Floor in a Sorted Array	Day45.java
46	Array	Largest in Array	Day46.java
47	Array	Value equal to index value	Day47.java
48	Array	Alternate Positive Negative	Day48.java
49	Array	Two Stacks in an Array	Day49.java
50	Array	Array End Insert	Day50.java

---

🛠 Detailed Solutions

Categorized logic and complexity for each problem.

🔹 Array

Day 1: Second Largest

• Problem: Find the second largest element in a positive integer array.
• Logic:
  1. Initialize largest = -1, secondLargest = -1.
  2. One pass: Update largest and secondLargest accordingly.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 2: Reverse an Array

• Problem: In-place array reversal.
• Logic: Two-pointer swap.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 3: Move All Zeroes to End

• Problem: Shift 0s while preserving order.
• Logic: Fill non-zeroes first, then pad remaining indices with 0.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 4: Rotate Array

• Problem: Counter-clockwise rotation by d steps.
• Logic: Reversal algorithm (reverse [0..d-1], [d..n-1], then all).
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 5: Next Permutation

• Problem: Lexicographically next greater permutation.
• Logic: Find pivot, swap with smallest larger value to right, reverse suffix.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 6: Stock Buy and Sell – Max one Transaction

• Problem: Maximize profit by buying once and selling once.
• Logic: Track minimum price seen so far and calculate potential profit at each step.
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 7: Majority Element - More Than n/3

• Problem: Find all elements that appear more than $n/3$ times.
• Logic: Boyer-Moore Voting algorithm with two candidates and a second pass for verification.
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 8: Kadane's Algorithm

• Problem: Find the maximum sum of a contiguous subarray.
• Logic: Maintain currMax and globalMax, resetting currMax to 0 if it becomes negative.
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 9: Stock Buy and Sell – Multiple Transaction

• Problem: Maximize profit by buying and selling multiple times.
• Logic: Accumulate profit whenever the current price is higher than the previous day's price.
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 10: Maximum Product Subarray

• Problem: Find the contiguous subarray within an array that has the largest product.
• Logic: Track both maximum and minimum product (for negative numbers) ending at the current position.
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 11: Minimize the Heights II

• Problem: Minimize the difference between tallest and shortest tower after adding/subtracting $k$.
• Logic: Sort the array and check potential min/max height differences at each gap.
• Complexity: $O(n \log n)$ Time, $O(1) $ Space.

Day 12: Smallest Positive Missing

• Problem: Find the smallest positive integer missing from an unsorted array.
• Logic: Use index-marking (negating values at specific indices) to track seen numbers in-place.
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 13: Repetitive Addition of Digits

• Problem: Repeatedly add digits until a single-digit number is obtained.
• Logic: Iterative digit sum calculation or using the digital root formula.
• Complexity: $O(\log_{10} n)$ Time, $O(1) $ Space.

Day 14: Last Moment Before Ants Fall Out

• Problem: Find the time when the last ant falls off a plank.
• Logic: Ants passing each other is equivalent to them "passing through" each other; find the max distance any ant travel.
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 15: Split Array in Three Equal Sum Subarrays

• Problem: Determine if array can be split into 3 parts with equal sum.
• Logic: Calculate total sum, check for divisibility by 3, and find cumulative sum breakpoints.
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 16: Maximize Number of 1's

• Problem: Find the max consecutive 1s after flipping at most $k$ zeros.
• Logic: Sliding window approach tracking the number of zeros in the current window.
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 17: Max Circular Subarray Sum

• Problem: Find max subarray sum in a circular array.
• Logic: Result is max(Kadane(arr), TotalSum - MinKadane(arr)).
• Complexity: $O(n)$ Time, $O(1) $ Space.

Day 29: Min and Max in Array

• Problem: Find the minimum and maximum elements in an array.
• Logic: Single pass comparison to update min and max values.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 30: Indexes of Subarray Sum

• Problem: Find a continuous subarray whose sum equals a target.
• Logic: Two-pointer (sliding window) approach to maintain the current sum.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 31: Minimum Jumps

• Problem: Minimum jumps to reach the end of the array.
• Logic: Greedy approach tracking the maximum reachable index and updating jumps at each step.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 32: Array Leaders

• Problem: Find all elements that are greater than or equal to all elements to their right.
• Logic: Traverse from right to left, keeping track of the maximum element seen so far.
• Complexity: $O(n)$ Time, $O(n)$ Space (for output).

Day 33: Array Duplicates

• Problem: Find all duplicates in an array containing elements from 1 to n.
• Logic: Use the array itself as a hash table by negating values at indices corresponding to the element values.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 34: Sort 0s, 1s and 2s

• Problem: Sort an array of 0s, 1s, and 2s without built-in functions.
• Logic: Dutch National Flag algorithm using three pointers (low, mid, high).
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 35: Kth Smallest

• Problem: Find the Kth smallest element in an array.
• Logic: QuickSelect algorithm (average $O(n)$) or PriorityQueue ($O(n \log k)$).
• Complexity: $O(n)$ Average Time, $O(1)$ Space.

Day 36: Parenthesis Checker

• Problem: Determine if an expression with brackets is balanced.
• Logic: Use a stack to match opening and closing brackets in the correct order.
• Complexity: $O(n)$ Time, $O(n)$ Space.

Day 37: Missing And Repeating

• Problem: Find one missing and one repeating number in range 1 to n.
• Logic: Index-based marking or mathematical sum/square sum differences.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 38: Array Search

• Problem: Find the first occurrence of an element x in an array.
• Logic: Linear search through the array.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 39: Array Subset

• Problem: Determine whether array b is a subset of array a.
• Logic: Frequency map using a HashMap to store counts of elements in array a.
• Complexity: $O(n+m)$ Time, $O(n)$ Space.

Day 40: Detect Loop in Linked List

• Problem: Determine if a singly linked list contains a loop.
• Logic: Floyd's Cycle-Finding algorithm (Slow and Fast pointers).
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 41: BFS of graph

• Problem: Perform BFS traversal starting from vertex 0.
• Logic: Queue-based level-by-level traversal using a visited array.
• Complexity: $O(V+E)$ Time, $O(V)$ Space.

Day 43: Missing in Array

• Problem: Find the missing element in a permutation of 1 to n.
• Logic: Use the sum formula n*(n+1)/2 or XOR all elements and numbers from 1 to n.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 44: Equilibrium Point

• Problem: Find the first index where sum of left elements equals sum of right elements.
• Logic: Precalculate total sum and subtract elements while traversing to find the point.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 45: Floor in a Sorted Array

• Problem: Find the largest element less than or equal to x.
• Logic: Binary search to find the rightmost valid candidate.
• Complexity: $O(\log n)$ Time, $O(1)$ Space.

Day 46: Largest in Array

• Problem: Find the largest element in an array.
• Logic: Single pass maximum tracking.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 47: Value equal to index value

• Problem: Find elements whose value equals their 1-based index.
• Logic: Linear scan checking arr[i] == i + 1.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 48: Alternate Positive Negative

• Problem: Rearrange array into alternating positive/negative numbers.
• Logic: Separate positives and negatives into two lists and merge them alternately.
• Complexity: $O(n)$ Time, $O(n)$ Space.

Day 49: Two Stacks in an Array

• Problem: Implement two stacks in a single fixed-size array.
• Logic: Grow stack 1 from left to right and stack 2 from right to left.
• Complexity: $O(1)$ push/pop, $O(n)$ Space.

Day 50: Array End Insert

• Problem: Insert a value at the end of an array or ArrayList.
• Logic: Direct assignment at index or using ArrayList.add().
• Complexity: $O(1)$ Time, $O(1)$ Space.

🔹 String

Day 18: Anagram

• Logic: Frequency array (size 26) counting.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 19: Non Repeating Character

• Problem: Return the first non-repeating character in a string.
• Logic: Frequency map (int[26]) plus a second pass to find the first character with count 1.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 20: Search Pattern

• Problem: Print all 0-based indexes of pattern pat in text txt.
• Logic: Sliding window string matching or KMP algorithm for efficiency.
• Complexity: $O(n \times m)$ Time, $O(1)$ Space.

Day 21: Min Chars to Add for Palindrome

• Problem: Min characters to add at the front to make a string a palindrome.
• Logic: LPS array from KMP on s + "#" + reverse(s).
• Complexity: $O(n)$ Time, $O(n)$ Space.

Day 22: Fizz Buzz

• Problem: Classic FizzBuzz up to n.
• Logic: Loop through numbers, check divisibility by 3, 5, or both (15).
• Complexity: $O(n)$ Time, $O(n)$ Space.

Day 23: Palindrome Sentence

• Problem: Check if a sentence is a palindrome after cleaning non-alphanumeric chars.
• Logic: Two-pointer approach bypassing non-alphanumeric characters.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 24: CamelCase Pattern Matching

• Problem: Match words against a capital letter pattern.
• Logic: Extract all capital letters from each word and check if the pattern is a prefix.
• Complexity: $O(N \times L)$ Time, $O(L)$ Space.

Day 25: Longest Prefix Suffix

• Problem: Find the length of the longest proper prefix which is also a suffix.
• Logic: Preprocessing step of KMP (building the LPS array).
• Complexity: $O(n)$ Time, $O(n)$ Space.

Day 26: Add Binary Strings

• Problem: Return the sum of two binary strings.
• Logic: Right-to-left addition with carry propagation, then reverse and clean leading zeros.
• Complexity: $O(n)$ Time, $O(n)$ Space.

Day 27: Implement Atoi

• Problem: Convert a string to an integer without built-in functions.
• Logic: Handle leading spaces, signs, and digits with overflow checks.
• Complexity: $O(n)$ Time, $O(1)$ Space.

Day 28: Minimum repeat to make substring

• Problem: Min times s1 must repeat to contain s2 as a substring.
• Logic: Repeatedly append s1 until length >= s2, check twice with KMP.
• Complexity: $O(n + m)$ Time, $O(m)$ Space.

🔹 Dynamic Programming & Graphs

Day 42: Number of Valid Parentheses

• Equivalent to: Catalan Number $C_n = \frac{1}{n+1} \binom{2n}{n}$.
• Method: Tabulation for optimal sub-structure.
• Complexity: $O(n^2)$ Time, $O(n)$ Space.

Day 41: BFS of Graph

• Method: Queue-based level traversal.
• Complexity: $O(V+E)$.

---

🔧 Setup & Execution

To run any solution locally:

1. Clone the repository:

   git clone https://github.com/VIJAYAPANDIANT/GeeksforGeeks.git

2. Navigate to the topic folder:

   cd Array

3. Compile and Run:

   javac Day1.java
   java Day1

---

📈 Complexity Summary

Best Case	Average Case	Worst Case
$O(1)$	$O(n)$	$O(n \log n)$

---

🤝 Connect

• GitHub: VIJAYA PANDIAN.T
• LinkedIn: VIJAYA PANDIAN.T

---

Happy Coding! 🎯