I recently encountered an interesting performance issue while solving the "Sereja and Brackets". I implemented a Segment Tree-based solution but found that my code was giving a "Time Limit Exceeded" (TLE) on the 13th test case. After some investigation, I discovered that the issue was related to how I was initializing a vector.
Originally, I was adding 3 elements to the vector using push_back() in a loop. To improve the performance, I decided to initialize the vector with a fixed size of 3 upfront, like this: vector t(3, 0). Surprisingly, this simple change made a huge difference, and my code passed all test cases with ease.
After some searching, I discovered that one reason for the performance hit is that when we use push_back() to add elements to a vector, the vector may need to be resized. This resizing involves allocating a new block of memory, copying the existing data to the new block, and then deallocating the old block. This process can be time-consuming, especially if the vector is large or the constraints are tight.
To avoid unnecessary resizing and copying, it's often a good idea to reserve enough space in the vector upfront to accommodate all the elements we need to add. This can be done using the reserve() function. By reserving enough space, we can ensure that the vector doesn't need to be resized as often, and that the performance of our code become much better.
Overall, this experience taught me the importance of carefully considering how vectors are initialized in performance-critical code.
Soltuion 1 link which got TLE
Soltuion 2 link which got accepted
