# Simple O(n) solution in C++ - Any optimisation?

• After banging my head against the wall to decipher the question, I have a O(n) solution
If you cant understand the problem see here: https://leetcode.com/discuss/1212/expected-output-of-abcde-4
I would still like to know if there is some optimization I can do to the algorithm.

Im reading the string one char at a time and creating the strings, in the end I just concat the strSpace according to the number of rows which is the solution

``````string convert(string s, int numRows){

std::string resultString = "";
std::string* strSpace = new std::string[numRows];

if(s.size() >= numRows && numRows > 1)
{
int index = 0;
int numDiagnols = 0;
for(std::string::iterator it = s.begin(); it != s.end(); ++it)
{
int iterIndex = it - s.begin();
if(index == numRows || numDiagnols > 0)
{
if(numDiagnols == 0)
{
numDiagnols = numRows - 2;
index = (numDiagnols > 0) ? 0 : 1;
}

strSpace[numDiagnols].push_back(s[iterIndex]);
--numDiagnols;
}
else
{
strSpace[index].push_back(s[iterIndex]);
numDiagnols = 0;
++index;
}
}

for(int i = 0; i < numRows; ++i)
{
resultString += strSpace[i];
}
}
else
{
resultString = s;
}

return resultString;
}``````

• ``````    class Solution {
public:
int minimumTotal(vector<vector<int>> &triangle) {
if(triangle.size()==0)
return 0;
if(triangle.size()==1)
return triangle[0][0];
vector<int> oldminpath;
vector<int> newminpath;
oldminpath.push_back(triangle[0][0]);
for(int i=1;i<triangle.size();i++)
{
newminpath.push_back(oldminpath[0]+triangle[i][0]);
for(int j=1;j<triangle[i].size()-1;j++)
newminpath.push_back(min(oldminpath[j-1]+triangle[i][j],oldminpath[j]+triangle[i][j]));
newminpath.push_back(oldminpath[i-1]+triangle[i][i]);
oldminpath=newminpath;
newminpath.clear();
}
int mymin=oldminpath[0];
for(int i=0;i<oldminpath.size();i++)
if(mymin>oldminpath[i])
mymin=oldminpath[i];
return mymin;
}
};

This one is more compact.``````

• How many ms?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.