6
\$\begingroup\$

Immediate Smaller Element The code is working fine Code is here. For each element in the array, check whether the right adjacent element (on the next immediate position) of the array is smaller. If the next element is smaller, print that element. If not, then print -1. The only problem is I'm getting "Time Limit Exceeded" when I submit my answer here. It shows

Your program took more time than expected.Time Limit Exceeded
Expected Time Limit < 3.496sec
Hint: Please optimize your code and submit again.

How do I optimize my code to pass the time limit exceeded problem?


Problem Statement: Given an integer array of size N. For each element in the array, check whether the right adjacent element (on the next immediate position) of the array is smaller. If next element is smaller, print that element. If not, then print -1.

Input: The first line of input contains an integer T denoting the number of test cases. T testcases follow. Each testcase contains 2 lines of input: The first line contains an integer N, where N is the size of array. The second line contains N integers(elements of the array) sperated with spaces.

Output: For each test case, print the next immediate smaller elements for each element in the array.

Constraints:
1 ≤ T ≤ 200
1 ≤ N ≤ 10E7
1 ≤ arr[i] ≤ 1000
Expected Time Limit < 3.496sec

Example:

Input:
2
5
4 2 1 5 3
6
5 6 2 3 1 7

Output:
2 1 -1 3 -1
-1 2 -1 1 -1 -1

Explanation:
Testcase 1: Array elements are 4, 2, 1, 5, 3. Next to 4 is 2 which is smaller, so we print 2. Next of 2 is 1 which is smaller, so we print 1. Next of 1 is 5 which is greater, so we print -1. Next of 5 is 3 which is smaller so we print 3. Note that for last element, output is always going to be -1 because there is no element on right.


Here is my code

class Program
{
    static void Main(string[] args)
    {
        int testCases = int.Parse(Console.ReadLine().Trim());

        while (testCases-- > 0)
        {
            int arrSize = int.Parse(Console.ReadLine().Trim());
            string[] arr = Console.ReadLine().Trim().Split(' ');

            for (int i = 0; i < arrSize - 1; i++)
            {
                if (int.Parse(arr[i]) > int.Parse(arr[i + 1]))
                {
                    Console.Write(arr[i + 1] + " ");
                }
                else
                    Console.Write("-1" + " ");
            }
            Console.Write("-1");
            Console.WriteLine();
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ In cases like this you might want to profile the code to see where you are spending the most time. In some languages that might require you to break the solution up into multiple functions. \$\endgroup\$ – pacmaninbw Aug 25 at 14:40
6
\$\begingroup\$

Things to improve

  • You are looping over the input twice; (1) when splitting the raw input string Console.ReadLine().Trim().Split(' ') (2) when going over the splitted items for (int i = 0; i < arrSize - 1; i++). Try finding a way to go over the raw input in a single pass.
  • You are parsing most items twice, once as arr[i+1] and once as arr[i] in the next cycle. Try avoiding redundant parsing.
  • Writing to the console is time expensive. Console.Write("-1" + " "); Try to find a way to build the string and write the result to the console once.

I just tested a solution taking into account the above and I got Execution Time: 1.21. So it's definately possible to go < 3.496

\$\endgroup\$
  • 1
    \$\begingroup\$ Lazy parsing seems like the next step to investigate. A lot of time is wasted splitting strings up, copying substrings around, etc. \$\endgroup\$ – Alexander Aug 25 at 22:41
  • \$\begingroup\$ Thanks a lot for your reply. It solved my problem. But, 1.Link How may I optimize code further? 2."You are looping over the input twice..Try finding a way to go over the raw input in a single pass." - I could not figure out this. May you tell me how to do that? 3."I just tested a solution taking into account the above and I got Execution Time: 1.21"- May you share your code with me? Thanks. \$\endgroup\$ – nahid Aug 29 at 7:13
  • \$\begingroup\$ I suggest you ask a follow-up question with your updated code :) \$\endgroup\$ – dfhwze Aug 29 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.