Comprehensive collection of classic array and matrix algorithms including dynamic programming, prefix sums, spiral traversal, and mathematical puzzles.
Master fundamental array and matrix manipulation techniques through 10 algorithm challenges covering dynamic programming, optimization problems, and mathematical patterns.
TP_2/
├── LIS.java # Longest Increasing Subsequence (DP)
├── Pivots.java # Find pivot elements
├── Spirale.java # Generate spiral matrix
├── MaxRectangle.java # Largest rectangle in binary matrix
├── PermutationCirculaire.java # Check circular permutation
├── Kadane.java # Maximum subarray sum
├── Majoritaire.java # Find majority element
├── ElementsManquants.java # Find missing elements
├── Diagonales.java # Compare diagonal sums
└── CarreMagique.java # Verify magic square
Problem: Find length of longest strictly increasing subsequence in array.
Approach: Dynamic Programming O(n²)
// dp[i] = length of LIS ending at index i
for (int i = 0; i < n; i++) {
dp[i] = 1; // Base case
for (int j = 0; j < i; j++) {
if (t[j] < t[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return max(dp);Example:
- Input:
[2, 1, 4, 2, 3, 5, 1, 7] - LIS:
[1, 2, 3, 5, 7]→ Length = 5
Screenshot: 
- LIS results for various test cases
Problem: Find elements where all left values ≤ pivot and all right values ≥ pivot.
Efficient Solution: Prefix Max + Suffix Min (O(n))
// Build prefixMax and suffixMin
for (int i = 1; i < n - 1; i++) {
if (prefixMax[i-1] <= t[i] && suffixMin[i+1] >= t[i]) {
// t[i] is a pivot
}
}Example:
- Input:
[3, 3, 3, 3] - Pivots:
3 3(middle elements)
Screenshot: 
- Pivot detection results
Problem: Generate n×n matrix filled in spiral order (1 to n²).
Pattern:
n=3: n=4:
1 2 3 1 2 3 4
8 9 4 12 13 14 5
7 6 5 11 16 15 6
10 9 8 7
Algorithm: Track boundaries (top, bottom, left, right) and fill layer by layer.
Screenshot: 
- Spiral matrices for n=1,2,3,4,5
Problem: Find largest rectangle containing only 1s in binary matrix.
Approach: For each row, treat as base and use histogram technique.
Example:
{0,1,1,0,1},
{1,1,1,1,0},
{1,1,1,1,0},
{1,1,0,0,1}Result: Area = 8 (rectangle at rows 1-2, cols 0-3)
Screenshot: 
- Code and output showing max rectangle
Problem: Check if array is circular permutation of another by rotating.
Approach: Concatenate first array with itself and search for second array.
Example:
{4,5,1,2,3} and {1,2,3,4,5} → true (rotation exists)
{4,5,1,2,3} and {2,3,4,5,1} → trueScreenshot: 
- Circular permutation test results
Problem: Find contiguous subarray with maximum sum.
Algorithm:
int maxSum = t[0], currentSum = t[0];
for (int i = 1; i < n; i++) {
currentSum = Math.max(t[i], currentSum + t[i]);
maxSum = Math.max(maxSum, currentSum);
}Example:
- Input:
[-2, 1, -3, 4, -1, 2, 1, -5, 4] - Output:
6(subarray:[4, -1, 2, 1])
Screenshot: 
- Kadane algorithm output (result: 6)
Problem: Find element appearing more than n/2 times.
Algorithm:
// Phase 1: Find candidate
int candidate = t[0], count = 1;
for (int i = 1; i < n; i++) {
if (count == 0) candidate = t[i];
count += (t[i] == candidate) ? 1 : -1;
}
// Phase 2: Verify candidateExample:
- Input:
[3, 3, 4, 3, 5] - Output:
3(appears 3 times out of 5)
Screenshot: 
- Majority element output (result: 3)
Problem: Find all missing elements in range [1, n] given array of size n-k.
Approach: Use boolean array or mathematical sum comparison.
Example:
- Input:
[1, 3, 5](n=5) - Output:
2 4(missing elements)
Screenshot: 
- Missing elements output (2 4)
Problem: Calculate and compare main diagonal and secondary diagonal sums.
Formula:
// Main diagonal: sum of m[i][i]
// Secondary diagonal: sum of m[i][n-1-i]Example:
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
- Main: 1+5+9 = 15
- Secondary: 3+5+7 = 15
- Difference = 0
Screenshot: 
- Diagonal comparison output
Problem: Check if n×n matrix is a magic square (all rows, columns, diagonals have same sum).
Conditions:
- All row sums equal
- All column sums equal
- Both diagonal sums equal
- All sums equal to magic constant: n(n²+1)/2
Example:
{8, 1, 6},
{3, 5, 7},
{4, 9, 2}
All sums = 15 → Magic Square ✓
Screenshot: 
- Magic square verification (Carré magique)
| Algorithm | Time | Space | Technique |
|---|---|---|---|
| LIS | O(n²) | O(n) | Dynamic Programming |
| Pivots | O(n) | O(n) | Prefix/Suffix arrays |
| Spirale | O(n²) | O(n²) | Layer traversal |
| MaxRectangle | O(n²m) | O(m) | Histogram technique |
| Permutation | O(n) | O(1) | String matching |
| Kadane | O(n) | O(1) | Greedy/DP |
| Majoritaire | O(n) | O(1) | Boyer-Moore |
| Missing | O(n) | O(n) | Boolean marking |
| Diagonales | O(n²) | O(1) | Matrix traversal |
| CarreMagique | O(n²) | O(1) | Sum verification |
- Break problem into overlapping subproblems
- Store solutions to avoid recomputation
- Build solution bottom-up or top-down with memoization
- Precompute cumulative information
- Answer queries in O(1) after O(n) preprocessing
- Common for range queries
- Track local and global maximum
- Decide to extend or start new subarray
- Classic greedy approach
- Find majority element in O(1) space
- Candidate selection + verification phases
- Optimal for frequency problems
# Compile individual file
javac LIS.java
java LIS
# Compile all
javac *.java
# Run specific algorithm
java Pivots
java Kadane
java CarreMagiqueLIS: Empty, single, decreasing, increasing, mixed Pivots: Sorted, reverse, duplicates, no pivots Spiral: n=1 to n=5 Kadane: All negative, all positive, mixed Majority: Clear majority, no majority Magic Square: Valid and invalid squares
- Dynamic Programming - Store intermediate results for optimal solutions
- Prefix/Suffix - Precompute for efficient range queries
- Greedy Algorithms - Make locally optimal choices (Kadane)
- Space-Time Tradeoff - Use extra space to improve time complexity
- Mathematical Patterns - Recognize formulas (magic square constant)
- Java - Core arrays and matrix manipulation
- Algorithms - Dynamic Programming, Greedy, Prefix Sums