# C# O(N) Accepted solution with comments

• ``````public IList<string> FullJustify(string[] words, int maxWidth)
{
// This solution is O(n) because even though we have a nested while loop, each element in the array is only visited twice
// This is not including the loops to fill out string with spaces. (I've assumed that these loops are of constant time complexity because the max numebr of spaces added to a string is maxWidth)

var result = new List<string>();
if (words.Length == 0) return result;
if (maxWidth == 0) return words.ToList();

if (words.Length == 1)
{
var str2 = words[0];
for (int i = 0; i < maxWidth-words[0].Length; i++)
{
str2+=" ";
}
return result;
}

var index = 0; var secondindex = 0;
var lengthwithspaces = 0; // keeps track of the length of word + minimum white space required
var actuallength = 0; // keeps track of the actual length of words, without including white space.
var numspacesrequired = 0; // keeps track of num of white spaces required for a string. Can be calculated from
// index and secondindex values as well, but this way seemed better to me.
var list = new List<string>();
while (index < words.Length)
{
var prev = lengthwithspaces; // Everytime we check lengthwithspaces, we're adding the extra 1 length for space.
// suppose we add a word and that fits maxWidth perfectly, the +1 will give us the incorrect value, so the if
// block contains both checks. Hence I've used prev.
lengthwithspaces += words[index].Length+1;

if (lengthwithspaces >= maxWidth && prev+words[index].Length > maxWidth)
{
// We need to reduce the numspacesrequired because we incremented on par with number of words added, but
// we only need (num of words - 1). If there are three words, we only need two spaces.
numspacesrequired--;
var reminder = 0;
var totalspaceslength = (maxWidth - actuallength);

// The idea of doing two whitespace variables is to evenly spread out the white spaces between the words.
// We just need two, since the white spaces will only be of length divisor or divisor+1. The idea is to
// divide the total length of white spaces with num of white spaces, so that we figure out how many white
// spaces the variable needs to have.

var divisor = (numspacesrequired == 0) ? 0 : totalspaceslength/numspacesrequired;
reminder = (numspacesrequired == 0) ? 0 : totalspaceslength%numspacesrequired;
var whitespace1 = ""; var whitespace2 = "";

for (int i = 0; i < divisor; i++)
{
whitespace1 += " ";
whitespace2 += " ";
}
if (reminder != 0) whitespace1 += " "; // All white spaces won't be of equal length
var str = "";

while (secondindex < index)
{
str += words[secondindex];
// for all the words that need to be added into the last sentence, append them with the
// appropriate space values.
if (secondindex != index-1)
{
if (numspacesrequired > 0 && reminder > 0)
{str += whitespace1;}
else if (numspacesrequired > 0 && divisor != 0)
{str += whitespace2; }
}
else
{
// Fill out the string with spaces to make it as long as maxWidth
if (str.Length < maxWidth)
{
var len = str.Length ;
while (len < maxWidth)
{
str += " "; len++;
}
}
}
reminder--;
numspacesrequired--;
secondindex++;
}
// reset the values.
lengthwithspaces = 0;
actuallength = 0;
numspacesrequired = 0;
}
else
{
// increment the values.
actuallength += words[index].Length;
index++;
numspacesrequired++;
}
}

// Add the last string to the list.
// Because this is the last line, we will simply add a normal " ", and fill out the end with spaces.
// As per the last line in the question.
var reminder1 = 0;
var totalspaceslength1 = (maxWidth - actuallength);
var divisor1 = (numspacesrequired == 0) ? 0 : totalspaceslength1/numspacesrequired;
reminder1 = (numspacesrequired == 0) ? 0 : totalspaceslength1 % numspacesrequired;
var whitespace11 = " ";

var str1 = "";
// for all the words that need to be added into the last sentence, append them with a single space.
while (secondindex < index)
{
str1 += words[secondindex];
if (secondindex != index-1)
{
if (numspacesrequired > 0) str1 += whitespace11;
}
numspacesrequired--;
secondindex++;
}
lengthwithspaces = 0;
actuallength = 0;
numspacesrequired = 0;

if (str1.Length < maxWidth)
{
// Fill out the string with spaces to make it as long as maxWidth
var len1 = str1.Length ;
while (len1 < maxWidth)
{
str1 += " "; len1++;
}
}