Leetcode with dani
Kanalga Telegram’da o‘tish
Join us and let's tackle leet code questions together: improve your problem-solving skills Preparing for coding interviews learning new algorithms and data structures connect with other coding enthusiasts
Ko'proq ko'rsatish1 240
Obunachilar
Ma'lumot yo'q24 soatlar
-47 kun
-2230 kun
Postlar arxiv
1 240
https://leetcode.com/problems/remove-linked-list-elements/
Easy question for beginner to linked list
26 Fev 2025, 11:48
1 240
Repost from Codeforces Official
Educational Codeforces Round 175
(rated for Div. 2) starts on the 27th of February at 14:35 UTC.
Please, join by the link https://codeforces.com/contests/2070
26 Fev 2025, 10:20
1 240
🚀 A2SV Internship Program – Level Up Your Tech Skills! 🚀
Gain hands-on experience in Frontend, Backend, Mobile Development, UI/UX, and Product Management while working on real projects with industry experts. Perfect for students looking to grow and launch their tech careers!
📌 Requirements: Must be a continuing student in their internship phase and have completed or be enrolled in A2SV’s G6 program.
📍 Location: Abrehot Library (In-person)
⏰ Hours: 9 AM - 12 PM, 2 PM - 6 PM (G6: 2 PM - 4 PM)
Apply now and start your journey with A2SV! 🚀
26 Fev 2025, 10:13
1 240
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
s = {0:-1}
t = 0
maxm = 0
c1 = 0
c0 = 0
for i in range(len(nums)):
if nums[i]:
c1+=1
else:
c0+=1
if c1-c0 not in s:
s[c1-c0] = i
else:
maxm = max(maxm,i-s[c1-c0])
return maxm24 Fev 2025, 13:25
1 240
▎LeetCode Problem 525: Contiguous Array
Difficulty: Medium
Topics: Array, Hashing, Prefix Sum
Companies: Many top tech companies have featured similar problems in interviews
Link: Contiguous Array on LeetCode
---
▎Problem Statement
Given a binary array
nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
A contiguous subarray is one where the elements are consecutive, and an equal number of 0s and 1s means that the sum (after a transformation) is 0.
Note:
• You can transform the array by replacing each 0 with -1.
• Then, the problem reduces to finding the largest subarray whose sum is 0.
---
▎Examples
Example 1:
Input: nums = [0, 1]
Output: 2
Explanation: The entire array [0, 1] has one 0 and one 1.
Example 2:
Input: nums = [0, 1, 0]
Output: 2
Explanation: Either subarray [0, 1] or [1, 0] has an equal number of 0s and 1s.
---
▎Approach Explanation
1. Transform the Array:
Replace every 0 with -1. This way, a subarray with an equal number of 0s and 1s will have a total sum of 0.
2. Prefix Sum Hash Map:
• Prefix Sum: Compute the cumulative sum while iterating through the transformed array.
• Hash Map: Use a dictionary to store the first occurrence of each cumulative sum.
• Finding a Subarray: If the same cumulative sum is seen again, the subarray between these two indices has a sum of 0 (equal number of 0s and 1s).
• Update Maximum Length: Calculate the length of the subarray and update the maximum length if this subarray is longer.
3. Efficiency:
This approach works in O(n) time and O(n) space, making it efficient for large inputs.
---
▎ Solution
def findMaxLength(nums):
# Replace 0 with -1 for transformation
for i in range(len(nums)):
if nums[i] == 0:
nums[i] = -1
cumulative_sum = 0
max_length = 0
sum_index_map = {} # To store the first occurrence of each cumulative sum
for i, num in enumerate(nums):
cumulative_sum += num
# Check if cumulative_sum is 0, which means subarray from index 0 to i is valid
if cumulative_sum == 0:
max_length = i + 1
# If cumulative_sum has been seen before, update max_length accordingly
if cumulative_sum in sum_index_map:
max_length = max(max_length, i - sum_index_map[cumulative_sum])
else:
sum_index_map[cumulative_sum] = i
return max_length
# Testing the function with provided examples
print(findMaxLength([0, 1])) # Output: 2
print(findMaxLength([0, 1, 0])) # Output: 2
▎Final Recap
This solution transforms the binary array into one that uses -1 instead of 0, so that we can use the cumulative sum to detect subarrays with equal numbers of 0s and 1s. By maintaining a hash map of the first occurrence of each cumulative sum, we can efficiently calculate the maximum length of any subarray with a sum of 0. This is a neat and efficient way to tackle the problem!
For more details, visit the problem link: Contiguous Array on LeetCode.24 Fev 2025, 13:18
1 240
Repost from Codeforces Official
Codeforces Round 1006 (Div. 3) will take place on the 25th of February at 14:35 UTC.
Please, join by the link https://codeforces.com/contests/2072?locale=en
24 Fev 2025, 10:46
1 240
▎Key Idea
Precompute the sums for each diagonal and anti-diagonal to quickly calculate the bishop’s attack sum for any cell.
▎Breakdown
▎1. Diagonals Identification:
• Main Diagonal (↘️): All cells share the same value of i - j (row index minus column index).
• Anti-Diagonal (↙️): All cells share the same value of i + j (row index plus column index).
▎2. Precomputation:
• Iterate through the chessboard and sum up the values for:
• Each main diagonal (grouped by i - j ).
• Each anti-diagonal (grouped by i + j ).
▎3. Calculating the Bishop’s Sum:
• When placing the bishop on a cell (i, j) :
• It attacks all cells on the main diagonal (i - j) and the anti-diagonal (i + j) .
• Since the cell (i, j) is included in both diagonal sums, subtract its value once to avoid double counting.
▎4. Finding the Maximum Sum:
• For every cell, calculate the total sum as:
total = (sum on main diagonal) + (sum on anti-diagonal) - (value of cell)• Keep track of the maximum sum across all cells. ▎Complete Python Code
def solve():
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
diag_main = {} # Sums for main diagonal (i - j)
diag_anti = {} # Sums for anti-diagonal (i + j)
# Precompute the sums for both types of diagonals
for i in range(n):
for j in range(m):
d1 = i - j
d2 = i + j
diag_main[d1] = diag_main.get(d1, 0) + board[i][j]
diag_anti[d2] = diag_anti.get(d2, 0) + board[i][j]
max_sum = 0
# Evaluate maximum bishop sum for every possible cell placement
for i in range(n):
for j in range(m):
d1 = i - j
d2 = i + j
# Sum of both diagonals minus the overlapping cell (i, j)
total = diag_main[d1] + diag_anti[d2] - board[i][j]
if total > max_sum:
max_sum = total
print(max_sum)
if __name__ == "__main__":
solve()
▎Summary of the Approach in Simple Terms: 1. For each cell, determine which main and anti-diagonals it belongs to. 2. Sum all values on each diagonal. 3. For each cell, the bishop's attack sum equals the sum of its main diagonal plus the sum of its anti-diagonal, minus the cell’s own value (to correct for double counting). 4. Find the maximum of these sums over all cells.
20 Fev 2025, 11:59
1 240
The key idea is to precompute the sums for each diagonal and anti-diagonal so that we can quickly calculate the bishop’s attack sum for any cell. Here’s a breakdown:
Diagonals Identification:
For the main (↘️) diagonal, all cells share the same value of i - j (row index minus column index).
For the anti-diagonal (↙️), all cells share the same value of i + j (row index plus column index).
Precomputation:
We iterate through the chessboard and add up the values for each main diagonal (grouped by i - j) and each anti-diagonal (grouped by i + j).
Calculating the Bishop’s Sum:
When placing the bishop on a cell (i, j), it attacks all cells on the main diagonal (i - j) and the anti-diagonal (i + j).
Since the cell (i, j) is included in both diagonal sums, we subtract its value once to avoid double counting.
Finding the Maximum Sum:
For every cell, calculate the total sum as:
total = (sum on main diagonal) + (sum on anti-diagonal) - (value of cell)
Keep track of the maximum sum across all cells.
Below is the complete Python code with these steps:
python
Copy
Edit
def solve():
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
diag_main = {} # Sums for main diagonal (i - j)
diag_anti = {} # Sums for anti-diagonal (i + j)
# Precompute the sums for both types of diagonals
for i in range(n):
for j in range(m):
d1 = i - j
d2 = i + j
diag_main[d1] = diag_main.get(d1, 0) + board[i][j]
diag_anti[d2] = diag_anti.get(d2, 0) + board[i][j]
max_sum = 0
# Evaluate maximum bishop sum for every possible cell placement
for i in range(n):
for j in range(m):
d1 = i - j
d2 = i + j
# Sum of both diagonals minus the overlapping cell (i, j)
total = diag_main[d1] + diag_anti[d2] - board[i][j]
if total > max_sum:
max_sum = total
print(max_sum)
if name == "main":
solve()
Summary of the Approach in Simple Terms:
Step 1: For each cell, determine which main and anti-diagonals it belongs to.
Step 2: Sum all values on each diagonal.
Step 3: For each cell, the bishop's attack sum equals the sum of its main diagonal plus the sum of its anti-diagonal, minus the cell’s own value (to correct for double counting).
Step 4: Find the maximum of these sums over all cells.
20 Fev 2025, 11:58
20 Fev 2025, ~11:58
1 240
check out this question
X-Sum
Timur has a chessboard where each square contains a non-negative number. He wants to place a bishop on the board such that the sum of the numbers in all the squares it can attack is maximized. The bishop attacks diagonally in all four directions (both the main diagonal and the anti-diagonal), and there is no limit to how far it can go in any diagonal direction. Note that the square where the bishop is placed is also counted in the sum.
Input:
The first number is an integer t, the number of test cases.
For each test case:
The first line contains two integers, n and m, representing the number of rows and columns.
This is followed by n lines, each containing m non-negative integers. These numbers are the values on the chessboard.
Output:
For each test case, output a single number: the maximum sum of the values from all the squares the bishop can attack when placed optimally on the board.
20 Fev 2025, 11:57
1 240
check this book if u have a problem of procrastinating , i liked it
19 Fev 2025, 12:49
1 240
class Solution:
def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
# Check for empty matrix
if not matrix or not matrix[0]:
return []
m, n = len(matrix), len(matrix[0])
result = []
row, col = 0, 0
# direction = 1 means moving up-right; direction = -1 means moving down-left.
direction = 1
while len(result) < m * n:
result.append(matrix[row][col])
if direction == 1: # Moving up-right.
# If we're at the last column, we can only go down.
if col == n - 1:
row += 1
direction = -1
# If we're at the top row, we can only go right.
elif row == 0:
col += 1
direction = -1
else:
row -= 1
col += 1
else: # direction == -1, Moving down-left.
# If we're at the bottom row, we can only go right.
if row == m - 1:
col += 1
direction = 1
# If we're at the first column, we can only go down.
elif col == 0:
row += 1
direction = 1
else:
row += 1
col -= 1
return result19 Fev 2025, 04:15
1 240
▎Problem Title: Diagonal Traverse
▎Difficulty: Medium
▎Problem Statement:
Given an m x n matrix mat, return an array of all the elements of the matrix in a diagonal order.
▎Examples:
▎Example 1:
Input:
mat = [[1,2,3],
[4,5,6],
[7,8,9]]
Output:
[1,2,4,7,5,3,6,8,9]
▎Example 2:
Input:
mat = [[1,2],
[3,4]]
Output:
[1,2,3,4]
▎Constraints:
• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 10^4
• 1 <= m * n <= 10^4
• -10^5 <= mat[i][j] <= 10^5
▎Notes:
• The output array should represent the elements of the matrix traversed in a diagonal pattern.
• Ensure that the function handles different matrix sizes and shapes correctly.
19 Fev 2025, 04:12
1 240
if any one have good resources to lean programming u can send me with this bot @zprogramming_bot and i will share in this channel https://t.me/techresourcesnew
18 Fev 2025, 11:46
1 240
https://leetcode.com/problems/rotate-string/
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
return goal in (s + s)18 Fev 2025, 04:30
