Immediate Smaller Element Time Limit Exceeded

Question

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();
        }
    }
}

Answer 1

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}