for the strivers #SDESheetChallenge, should i just post the image of my solution or should i keep explaining it too?
(i see very less impressions on my explaining posts.)
Day 4 – #SDESheetChallenge@takeUforward_@striver_79
(a thread🧵)
Problem 1: Find the Duplicate Number
Approach:
1. Sort the array.
2. Traverse the array from left to right.
3. Compare each element with its previous element:
- If nums[i] == nums[i - 1],
a duplicate has been found.
4. Return the duplicate number.
5. If no duplicate is found, return -1.
Time Complexity: O(n log n)
Space Complexity: O(1)
#DSA #LeetCode #SDESheet #Cpp
Day 4 – #SDESheetChallenge@takeUforward_@striver_79
(a thread🧵)
Problem 1: Find the Duplicate Number
Approach:
1. Sort the array.
2. Traverse the array from left to right.
3. Compare each element with its previous element:
- If nums[i] == nums[i - 1],
a duplicate has been found.
4. Return the duplicate number.
5. If no duplicate is found, return -1.
Time Complexity: O(n log n)
Space Complexity: O(1)
#DSA #LeetCode #SDESheet #Cpp
Day 4 – #SDESheetChallenge@takeUforward_@striver_79
Problem 3: Count Inversions
Approach (Merge Sort):
1. Divide the array into two halves recursively until each subarray contains a single element.
2. Count inversions in:
- The left half
- The right half
3. During the merge step:
- If arr[left] <= arr[right],
add arr[left] to the temporary array.
- Otherwise,
add arr[right] to the temporary array and count:
(mid - left + 1) inversions.
This is because all remaining elements in the left half are greater than arr[right].
4. Merge the two sorted halves.
5. The total inversions are:
- Inversions in the left half
- Inversions in the right half
- Inversions found during merging
6. Return the total count.
Time Complexity: O(n log n)
Space Complexity: O(n)
#DSA #LeetCode #SDESheet #Cpp
Day 4 – #SDESheetChallenge@takeUforward_@striver_79
Problem 2: Repeat and Missing Number
Approach:
1. Calculate:
- Sum of all elements in the array.
- Sum of squares of all elements in the array.
2. Compute the expected values for numbers from 1 to n:
- Sum = n(n + 1) / 2
- Sum of Squares = n(n + 1)(2n + 1) / 6
3. Let:
- x = repeating number
- y = missing number
4. Form two equations:
-> x - y = (actual sum) - (expected sum)
-> x² - y² = (actual square sum) - (expected square sum)
5. Using:
-> x² - y² = (x - y)(x + y)
Find x + y.
6. Solve the two equations:
-> x - y
-> x + y
to obtain x (repeating number) and y (missing number).
7. Return {x, y}.
Time Complexity: O(n)
Space Complexity: O(1)
#DSA #LeetCode #SDESheet #Cpp
I can really relate to you.
Especially that how to make genuine connections now. Tbh i feel jitne genuine connections banne hote h vo school me bante h (my opinion). College me to 99% time sab 🐍 hote h.
And sometimes i feel ki i say ki sab 🐍 h but maybe I'm also the one like that only. Mai bhi kuch acchi nhi hu. I must've also behaved like a 🐍 with someone. And honestly it just messes with my head so much. And ab to maine genuine connections search krna hi band kr diya. And tbh iss sem meri ek dost bani thi. Which I felt was genuine. But now she has her 6 months intern and we are not really going to talk.
I just don't know ki kya hona chahiye kya nhi. I'm just going with the flow.
Day 3 – #SDESheetChallenge@takeUforward_@striver_79
Problem 3: Merge Sorted Array
Approach:
1. Start filling the array from the end.
- end = last index of nums1
2. Compare the last valid elements of both arrays:
- nums1[m - 1]
- nums2[n - 1]
3. Place the larger element at nums1[end].
4. Move the corresponding pointer and decrement end.
5. Continue until one of the arrays is exhausted.
6. If elements are still left in nums2,
copy them into nums1.
Time Complexity: O(m + n)
Space Complexity: O(1)
#DSA #LeetCode #SDESheet #Cpp
Day 3 – #SDESheetChallenge@takeUforward_@striver_79
a thread🧵
Problem 1: Rotate Image
Approach:
1. Transpose the matrix:
- Swap matrix[i][j] with matrix[j][i]
- Only process the upper triangular part to avoid double swapping
2. Reverse every row of the transposed matrix.
3. The matrix is now rotated by 90deg clockwise.
Time Complexity: O(n²)
Space Complexity: O(1)
#DSA #LeetCode #SDESheet #Cpp
Day 3 – #SDESheetChallenge@takeUforward_@striver_79
Problem 2: Merge Intervals
Approach:
1. Sort the intervals based on their starting points.
2. Initialize:
- x = start of the first interval
- y = end of the first interval
3. Traverse the remaining intervals:
- If the current interval starts after y:
• No overlap exists.
• Add [x, y] to the answer.
• Update x and y to the current interval.
- Otherwise:
• The intervals overlap.
• Extend the current interval by updating:
y = max(y, current end)
4. After the traversal, add the last merged interval to the answer.
5. Return the merged intervals.
Time Complexity: O(n log n)
Space Complexity: O(n)
#DSA #LeetCode #SDESheet #Cpp