I approached the problem by iterating through the array and compare each element with its next neighbor. I then compare the last element with the first.
As I iterate, every time I encounter a situation where the current element is greater than the next, I increase a counter. If this counter exceeds one, I immediately know the array couldn’t have come from a sorted array that was simply rotated, and I return false. If I complete the loop and find one or no drops, I return true.
My first approach was to traverse forward and backward to check the longest monotonic subarray but this approach will take a long time as I will have to traverse twice. Instead, I'll used two pointer.
I used two variables, inc_len and dec_len, to track the length of the current increasing and decreasing subarrays, respectively. As I traverse the array, I compare each element with the previous one. If the current element is greater, I increment inc_len and reset dec_len to 1. If it is smaller, I increment dec_len and reset inc_len to 1. If they are equal, I reset both counters to 1.
My approach started with two variables: max_sum to store the highest sum found and current_sum to keep track of the running sum of the current ascending subarray. Starting with the first element, I iterated through the array. If the current number is greater than the previous one, I will add it to current_sum. Otherwise, I will update max_sum if current_sum is larger, then reset current_sum to the current number.
At the end of the loop, I will return the maximum of max_sum and current_sum to account for the last subarray.
I first check if the two strings are already equal. If they are, I return True immediately since no swaps are needed. Otherwise, I identify the positions where the characters in s1 and s2 differ. I do this by iterating through both strings and collecting the indices where their characters do not match.
If the number of differences is more than two, I return False. If there is exactly one difference, I also return False since swapping requires at least two differing positions. However, if there are exactly two mismatches, I check whether swapping the mismatched characters in one of the strings would make the strings equal. If so, I return True; otherwise, I return False.
I approached the problem by counting the frequency of each product formed by multiplying two distinct numbers in the given array. I used a dictionary where the keys represent the product values, and the values store the count of how many times each product appears.
Once I built the frequency dictionary, I calculated the number of valid tuples. If a product appears count times, then I can select two pairs (a, b) and (c, d) from these count occurrences in count * (count - 1) / 2 ways. Since each selection results in 8 valid permutations of (a, b, c, d), I multiplied the computed value by 8 to get the final count.
In this approach, I used a dictionary ball_colors to keep track of the latest color assigned to each ball. Also, I added a set called distinct_colors to store all unique colors in use.
For each query [x, y], I first check if ball x has already been assigned a color. If it has and the color is different from y, I decrement the count of the old color in a dictionary color_count. If the count reaches zero, I remove the old color from distinct_colors. Then, I update ball x with the new color y and update its count in color_count. Finally, I add y to distinct_colors and append the size of distinct_colors to my result list.
Today is more of designing.
I took a heap-based approach to optimize finding the smallest index efficiently.
For the __init__ magic function, I created a dictionary index_to_number to map indices to their assigned numbers and another dictionary, number_to_indices, where each number maps to a min-heap that stores all indices containing that number.
This was uqite straightforward as I used a stack to track and remove the characters. I then iterated through the string character by character. If the character was a digit, I removed the closest non-digit character to its left by popping the top element from the stack (if it wasn’t empty). If the character was not a digit, I simply added it to the stack.
At the end of the process, the stack contained only the remaining characters. I then joined them together to form the final result and returned it.
I start by using a while loop to check if the substring part exists in s. As long as part is present, I keep removing the first occurrence of it using s.replace(part, "", 1). This ensures that I only remove one instance at a time, starting from the left. I repeat this process until part no longer appears in s. Once all instances are removed, I return the modified string.
class Solution:
def removeOccurrences(self, s: str, part: str) -> str: