This was in the "Hard" difficulty and vry tricky. I gave up and used the editorial
Ifihanagbara Olusheye Ifihan
🔧
My approach was using a hash map index_map to map each value in the array. Then I initialized a 2D dynamic programming table (dp) where dp[j][i] stores the length of the longest Fibonacci-like subsequence ending with elements at indices j and i. All values were initially set to 2, representing the minimum length of a valid Fibonacci sequence.
During iteration over all pairs of indices (i, j) with i > j, I calculated the potential previous element as arr[i] - arr[j]. If this element existed in the array with an index less than j, it indicated a valid extension of the Fibonacci sequence. I updated dp[j][i] accordingly and tracked the maximum length found using max_length.
Finally, I returned max_length if it was at least 3, indicating a valid Fibonacci-like subsequence.
I first initialized variables to track the maximum and minimum sums as well as the current sums while iterating through the array. At each step, I updated the current maximum and minimum sums by either extending the existing subarray or starting fresh with the current element. At the same time, I maintained the global maximum and minimum sums observed during the traversal.
Finally, I returned the greater value between the maximum sum and the absolute value of the minimum sum.
I started by using two counters: even_count and odd_count. First, I set even_count to 1 to account for an empty prefix sum, and odd_count to 0. As I iterated through the array, I accumulated the prefix sum and checked whether it was odd or even. When the prefix sum was even, I added the odd_count to the result since combining an even prefix sum with a prior odd prefix would result in an odd subarray sum. Conversely, if the prefix sum was odd, I added the even_count to the result, on the fact that an odd prefix sum paired with a prior even prefix sum also yields an odd subarray sum.
To handle large outputs, I kept the result modulo (10^9 + 7) throughout the process.
I first constructed a graph representation of the tree using an adjacency list. Then I started by determining Bob's exact path from his initial position to the root (node 0). Using a breadth-first search (BFS), I established the parent-child relationships within the tree. With this information, I traced Bob's route back to the root, storing the step count for each node on his path. This step count helped me handle scenarios where Alice and Bob might meet at a node.
To calculate Alice's maximum income, I implemented a depth-first search (DFS) to explore all possible paths Alice could take towards a leaf node. During this traversal, I managed the income calculations by checking whether Alice reached a node before, after, or at the same time as Bob. If they reached a node simultaneously, I halved the reward or cost at that gate. For leaf nodes, I directly returned the accumu
In my approach, I began by addressing the edge cases. If either array is empty, I return None. When the preorder array contains only one element, I construct and return a single-node tree with that element as the root.
To construct the tree, I first create the root node using the first element of the preorder array. The key observation here is that the left child of the root in the preorder traversal is also the root of the left subtree.
I then recursively build the left and right subtrees using the corresponding slices of the preorder and postorder arrays. The left subtree is constructed from elements before the identified boundary, while the right subtree uses elements beyond it. Then I return the constructed root node, which connects the full binary tree.
NewerOlder