Minimum sub-array challenge

Question

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<SubInterval> {
    public int start;
    public int end;

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

    public int CompareTo(SubInterval other) {
        if (this.Length > other.Length)
            return 1;
        else if (this.Length < other.Length)
            return -1;
        else if (this.Length == other.Length)
            return this.start < 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 < 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<int> lookup = new List<int>() { i };
    for (int k = i; k <= j; k++) {
        if (a[k] == 0) {
            min = 0;
            break;
        }
        if (a[k] < min) {
            min = a[k];
            lookup = new List<int>() { k };
        }
        else if (a[k] == min && k > 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 && lookup.Count > 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<int> samesLookup, int[] a) {
    List<SubInterval> list = new List<SubInterval>();
    SubInterval sub;
    for (int k = 0, ikj = 0; k < 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<SubInterval>();
}

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?

Here's the expected testcase output; it's the correct answer that was downloadable from hackerrank.com. — codeReview, Jun 16 at 10:46

rolfl · Accepted Answer · 2015-06-15 15:38:24Z

class SubInterval : IComparable<SubInterval> {
    public int start;
    public int end;

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

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

By using a constructor which takes the start and the end of the SubInterval and using properties instead of public fields, you could precalculate the Length property.

In a worst case scenario the CompareTo() method would calculate the length 3 times for the current instance and 3 times for the other instance.

I would go one step further by adding a method to set the end instead of using a public property. This would indicate that the one assignment of end is a special case and I could use auto-implemented properties.

I would like to encourage you to use braces {} for single command if statements too. This helps to make your code less error prone.

Declaring multiple variables on the same line like

int N, Q;
int[] a, q;

reduces the readability of the code. Also variables should be named using meaningful names otherwise one can't grasp the code at first glance.

Also there is no explicit rule where to place the opening brace { the usual C# developer will expect it on a new line.

Applying the above will lead to

class SubInterval : IComparable<SubInterval> 
{

    public int Start { get; private set;}
    public int End { get; private set;}

    public SubInterval(int start, int end)
    {
        Start = start;
        End = end;
        CalculateLength();
    }

    public void SetEnd(int end)
    {
        End = end;
        CalculateLength();
    }

    private void CalculateLength()
    {
        length = (start == 0 && end == 0) ? 0 : end - start + 1;
    }

    private int length = 0;
    public int Length { get { return length; } }

    public int CompareTo(SubInterval other)
    {
        if (this.Length > other.Length)
        {
            return 1;
        }
        else if (this.Length < other.Length)
        {
            return -1;
        }

        return this.start < other.start ? 1 : -1;
    }
}

Aside from the remarks on C# braces, this is helpful. I see how this may help if SubInterval.Length is called significantly more often than the end field is changed. It looks like the Length is called most often in the method getLongestSubInterval1s. So let's see if we see an improvement there. Your rewrite of the CompareTo would run faster, I'm sure. — codeReview, Jun 16 at 0:36
Even after trying the suggested optimizations, haven't yet reached a solution that meets the time limit requirements for C# as stated on the environment page. Let's accept your answer for now, and I plan to post a follow-up question on optimizing the solution to a similar type of problem. — codeReview, Jun 29 at 10:37

Heslacher · Answer 2 · 2015-06-15 14:09:42Z

up vote 6 down vote

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 > other.Length)
    return 1;
else if (this.Length < other.Length)
    return -1;
else if (this.Length == other.Length)
    return this.start < other.start ? 1 : -1;
else
    return 0;

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

if (this.Length > other.Length)
    return 1;
if (this.Length < other.Length)
    return -1;
return this.start < 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.

edited Jun 15 at 14:09

Heslacher
21.3k32682

answered Jun 15 at 13:54

janos♦
59.1k660234

For this problem, do the coders who implement the solution in C/C++ have a significant speed advantage over those who code in an interpreted language? Do you see any places where unsafe code can improve the speed substantially? – codeReview Jun 16 at 2:28

1

In my experience, faster languages don't have an advantage in such challenges. The important is the order of magnitude of the complexity of the solution. For example, if the designers of the challenge are looking for an \$O(N)\$ solution, then an \$O(N^2)\$ solution in even the fastest language will never pass. Also, when an \$O(N)\$ solution passes, an \$O(3N)\$ solution passes too, for example. – janos♦ Jun 16 at 6:00

your answer is good, but I'm going to edit my question, then wait another day or so, see if it catches the attention of anyone else, and hopefully someone will write an an answer that talks about the fastest possible solution for this problem, and how my code is falling short of it. Then I'll accept an answer. – codeReview Jun 16 at 9:44

1

My answer is far from good and I know it. My points are true, but not very important, and they don't help with your main question, which is the TLE. Heslacher's answer is better. You are free to leave your question open until you are happy to accept an answer (even if it doesn't fully answer you, but you are happy enough). I appreciate the sentiment though, so thanks ;-) – janos♦ Jun 16 at 10:04

1

Thanks for accepting, but this answer really doesn't deserve it. I really prefer you accept Heslacher's answer, it's much better than this one. – janos♦ Jun 29 at 5:00

add a comment |

asked	2 months ago
viewed	218 times
active	2 months ago

current community

your communities

more stack exchange communities

Minimum sub-array challenge

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged c# search time-limit-exceeded complexity or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Minimum sub-array challenge

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c# search time-limit-exceeded complexity or ask your own question.

Related

Hot Network Questions