Minimum sub-array challenge Below is my solution to finding the minimum product sub-interval. It passed 8/12 or so test cases, but the other test cases timed out if they hadn't finished within 2 seconds. When I compile this code as Release, optimized, and to target x64, it takes about 7.6 seconds to finish on large input sizes, such as  this testcase. (I'm running this on Windows 8.1 with CPU: AMD FX-8320 3.49 GHz). 

using System;
using System.Collections.Generic;
using System.Linq;


class SubInterval : IComparable&lt;SubInterval&gt; {
    public int start;
    public int end;

    public int Length { get { return start == 0 &amp;&amp; end == 0? 0 : end - start + 1; } }

    public int CompareTo(SubInterval other) {
        if (this.Length &gt; other.Length)
            return 1;
        else if (this.Length &lt; other.Length)
            return -1;
        else if (this.Length == other.Length)
            return this.start &lt; other.start ? 1 : -1;
        else
            return 0;
    }
}

class Solution {
    static void Main(string[] args) {
        int N, Q;
        int[] a, q;
        int[][] linesQ;

        //read from STDIN, initialize variables...

        System.Diagnostics.Stopwatch watch = System.Diagnostics.Stopwatch.StartNew();
        for (int j = 0; j &lt; Q; j++) {
            q = linesQ[j];
            if (q[0] == 2)
                a[q[1]] = q[2];
            else
                getMinSubInterval(a, q[1], q[2]);
        }
        watch.Stop();
        long ms = watch.ElapsedMilliseconds;   
}

static void getMinSubInterval(int[] a, int i, int j) {

    int min = a[i];
    List&lt;int&gt; lookup = new List&lt;int&gt;() { i };
    for (int k = i; k &lt;= j; k++) {
        if (a[k] == 0) {
            min = 0;
            break;
        }
        if (a[k] &lt; min) {
            min = a[k];
            lookup = new List&lt;int&gt;() { k };
        }
        else if (a[k] == min &amp;&amp; k &gt; i) {
            lookup.Add(k);
        }
    }


    if (min == 0) {
        SubInterval zero = new SubInterval { start = i, end = j };
        Console.WriteLine("0 {0} {1}", zero.start, zero.end);
    }
    else if (min == 1 &amp;&amp; lookup.Count &gt; 1) {
        SubInterval longest = getLongestSubInterval1s(lookup, a);
        Console.WriteLine("1 {0} {1}", longest.start, longest.end);
    }
    else  {
        int idxMin = lookup[0];
        SubInterval sub = new SubInterval { start = idxMin, end = idxMin };
        Console.WriteLine("{2} {0} {1}", sub.start, sub.end, a[idxMin]);
    }


}

static SubInterval getLongestSubInterval1s(List&lt;int&gt; samesLookup, int[] a) {
    List&lt;SubInterval&gt; list = new List&lt;SubInterval&gt;();
    SubInterval sub;
    for (int k = 0, ikj = 0; k &lt; samesLookup.Count; k++, ikj++) {

        if (k == 0 || !(a[samesLookup[k]] == a[ikj])) {
            sub = new SubInterval { start = samesLookup[k], end = samesLookup[k] };
            ikj = sub.start;
            list.Add(sub);
            continue;
        }
        (list[list.Count - 1]).end = samesLookup[k];
    }

    return list.Max&lt;SubInterval&gt;();
}


How can this code be improved upon so that it runs in \$ O(n \log(n)) \$ time, or what constant-time improvements can be made?
This review won't help much with your time limit exceeded problem,
but there are some poor practices in your code that I'd like to point out.



The else statement is dead code, and the last else if can be changed to else here:


if (this.Length &gt; other.Length)
    return 1;
else if (this.Length &lt; other.Length)
    return -1;
else if (this.Length == other.Length)
    return this.start &lt; other.start ? 1 : -1;
else
    return 0;



Actually, since all the if-else branches return,
you can simplify to:

if (this.Length &gt; other.Length)
    return 1;
if (this.Length &lt; other.Length)
    return -1;
return this.start &lt; other.start ? 1 : -1;




Method names that start with the word "get" normally return something.
getMinSubInterval is void, and it prints stuff.
So it would be better to rename it accordingly.