On the first day of my LeetCode journey, I found myself back in my hometown, amidst the bustling atmosphere of home renovation work taking place in our house. Despite the day's busy schedule, I was determined to embark on my coding journey. By the evening, I finally carved out some time to dive into the world of algorithms and problem-solving.
The challenge presented to me was centered around arrays, one of the fundamental data structures in computer science. Arrays, as many of you may know, are containers capable of holding a fixed number of elements of the same data type.
The specific problem I encountered was known as the "Running Sum of Array." In essence, I needed to calculate the running sum of an array, where each element in the resulting array at index i represents the sum of all elements from the beginning of the input array up to index i.
Here's an example to illustrate the problem:
Input: nums = [1, 2, 3, 4] Output: [1, 3, 6, 10] Explanation: The running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
To tackle this problem, I employed a simple yet effective approach by manipulating the input array directly. Here's the code snippet that accomplishes this task:
class Solution {
public int[] runningSum(int[] nums) {
for (int i = 1; i < nums.length; i++) {
nums[i] = nums[i - 1] + nums[i];
}
return nums;
}
}
This elegant solution iterates through the array, starting from the second element (i = 1) to the end. At each step, it updates the current element by adding the previous element, effectively building up the running sum as desired.
With my first LeetCode problem successfully conquered, I eagerly anticipated the challenges that the next days would bring on this exciting coding journey. Stay tuned for more updates as I continue to refine my problem-solving skills and share my insights along the way.
Day 2: Exploring Pascal's Triangle
Welcome back to my 28-day LeetCode journey! On day two, I encountered a fascinating problem involving Pascal's Triangle, a mathematical construct with deep connections to combinatorics and binomial coefficients. Let's dive into the problem and how I approached it.
Problem Description:
The task at hand was to generate Pascal's Triangle up to a given number of rows, represented as a list of lists. Each row in Pascal's Triangle is constructed by adding the two numbers directly above it, with the first and last elements of each row always being 1.
For example, when generating Pascal's Triangle with 5 rows, it should look like this:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
Solution Approach:
public List<List<Integer>> generate(int numRows) {
// Create a list of lists to store the entire triangle.
List<List<Integer>> allRows = new ArrayList<List<Integer>>();
// Initialize a single row list for the first row.
ArrayList<Integer> row = new ArrayList<Integer>();
// Iterate through numRows times to construct each row.
for (int i = 0; i < numRows; i++) {
// Add 1 to the beginning of the row (first element).
row.add(0, 1);
// Loop through the row starting from the second element.
for (int j = 1; j < row.size() - 1; j++) {
// Update the current element by adding the values from the previous row.
row.set(j, row.get(j) + row.get(j + 1));
}
// Add the completed row to the list of all rows.
allRows.add(new ArrayList<Integer>(row));
}
// Return the entire Pascal's Triangle.
return allRows;
}
Explanation:
We start by creating a list of lists called
allRowsto store the entire Pascal's Triangle.We initialize an
ArrayListcalledrowto represent each row as we generate them.Using a
forloop, we iteratenumRowstimes to create each row.In each iteration, we add
1to the beginning of therowlist, as the first and last elements of every row in Pascal's Triangle are always1.We then loop through the row starting from the second element (index
1). In this loop, we update each element by adding the values from the previous row at the corresponding positions.After updating the row, we add it to
allRowsas a newArrayListto ensure we capture the current state of the row.Finally, we return the complete Pascal's Triangle, stored in
allRows.
This approach effectively constructs Pascal's Triangle row by row, and by the end of the loop, allRows contains the entire triangle. It's a fascinating example of how simple mathematical concepts can be translated into code. Stay tuned for more exciting challenges on my 28-day LeetCode journey!
Day 3: Removing Duplicates from Sorted Array
As I delve deeper into my 28-day LeetCode journey, I'll be candid: there are moments when I hesitate to tackle these intricate problems. The mental fortitude and motivation required can be quite demanding. Yet, I persist because I firmly believe in the transformative power of practice.
Much like a newcomer embarking on a fitness journey, one might not immediately notice the physical changes. It's the gradual, persistent effort that yields results over time. In the world of coding, it's no different. Every problem solved, every line of code written, is a step forward.
In these 28 days, my goal is not just to master algorithms but to embrace the process of growth and improvement. I encourage you to do the same, whether you're a fellow coder on your own journey or someone considering taking that first step. Remember, progress isn't always immediately visible, but it's there, quietly shaping your skills and resilience.
So, let's keep pushing forward, one coding challenge at a time, and see where this journey takes us. Your commitment to practice, like mine, has the power to spark remarkable changes. Stay tuned for more insights and problem-solving as we continue this adventure together. 🚀
Problem statement:
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
Change the array
numssuch that the firstkelements ofnumscontain the unique elements in the order they were present innumsinitially. The remaining elements ofnumsare not important as well as the size ofnums.Return
k.Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Solution:
class Solution {
public int removeDuplicates(int[] nums) {
//if theres nothing in the array
if(nums.length==0)
return 0;
//theres two pointers one for moving the nos and other for returning the length.
int ui=0;
for(int i=1;i<nums.length;i++){
if(nums[i]!=nums[ui]){
ui++;
nums[ui]=nums[i];
}
}
return ui+1;
}
}
Day 4: Merge Intervals (Problem no. 56)
Problem:
Given an array of intervals where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
This seems an interesting problem, we need to merge the sub-arrays into single sub-arrays. If they don't have common values then just keep the subarray as it is.
Algorithm
Start
Check if there are any number of common
If they are common, then take that sub-array and next to it array and just take the first value and last value and make the sub-array.
If there's no common, then just keep the subarray as it is.
Return the array finally
Solution
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1) {
return intervals;
}
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> mergedIntervals = new ArrayList<>();
int[] currentInterval = intervals[0];
for (int i = 1; i < intervals.length; i++) {
int nextStart = intervals[i][0];
int nextEnd = intervals[i][1];
if (currentInterval[1] >= nextStart) {
currentInterval[1] = Math.max(currentInterval[1], nextEnd);
} else {
mergedIntervals.add(currentInterval);
currentInterval = intervals[i];
}
}
mergedIntervals.add(currentInterval);
int[][] result = new int[mergedIntervals.size()][2];
for (int i = 0; i < mergedIntervals.size(); i++) {
result[i] = mergedIntervals.get(i);
}
return result;
}
}
Day 5: Solving the 3Sum Problem (Problem No. 15)
Today, I encountered a classic problem in the world of algorithms: 3Sum. This problem, denoted as Problem No. 15 on LeetCode, challenges us to find all unique triplets in an array that sum up to zero.
Problem Description:
The 3Sum problem can be summarized as follows:
Given an array of integers, we need to find all unique triplets (three elements) in the array that sum up to zero.
For example, given the array [-1, 0, 1, 2, -1, -4], the solution is [[ -1, -1, 2 ], [ -1, 0, 1 ]].
Solution Approach:
Solving the 3Sum problem is a classic exercise in problem-solving and usually involves sorting the array and then using multiple pointers to efficiently find the triplets. Here's a detailed breakdown of how I approached this challenge:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
int lo = i + 1, hi = nums.length - 1, sum = -nums[i];
while (lo < hi) {
if (nums[lo] + nums[hi] == sum) {
result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
lo++;
hi--;
} else if (nums[lo] + nums[hi] < sum) {
lo++;
} else {
hi--;
}
}
}
}
return result;
}
}
Sorting: We start by sorting the
numsarray. Sorting simplifies the process of finding triplets with a specific sum.Three-Pointer Approach: We use a three-pointer approach with an outer loop,
i, and two inner pointers,loandhi.Duplicate Handling: To avoid duplicate triplets, we skip any identical elements as we iterate through the array.
Triplet Search: We calculate the
sumas the negation of the current elementnums[i]and search for a pair of elements in the subarraynums[lo]tonums[hi]that sums tosum.Triplet Found: When a valid triplet is found (i.e.,
nums[i] + nums[lo] + nums[hi] == 0), we add it to theresultlist as a list of three integers. We then move theloandhipointers, while skipping over any duplicate elements.Adjusting Pointers: Depending on whether the sum of the current pair is less than or greater than the target sum, we adjust the
loandhipointers accordingly.Return: Finally, we return the
resultlist containing all unique triplets that sum to zero.
This approach efficiently identifies all unique triplets that meet the criteria, making it an excellent exercise for mastering algorithms and data structures.