# 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<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) {
}
}

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;
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. Jun 16, 2015 at 10:46

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. Jun 16, 2015 at 0:36

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.

• 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? Jun 16, 2015 at 2:28
• 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. Jun 16, 2015 at 6:00