Otdfbt

How to make a villain when your PCs are villains?

I sent an angry e-mail to my interviewers about a conflict at my home institution. Could this affect my application?

What does the output current rating from an H-Bridge's datasheet really mean?

What made the Ancient One do this in Endgame?

How can I detect if I'm in a subshell?

Does an African-American baby born in Youngstown, Ohio have a higher infant mortality rate than a baby born in Iran?

Is there a risk to write an invitation letter for a stranger to obtain a Czech (Schengen) visa?

Any Volunteers for Card Counting?

How long would it take for sucrose to undergo hydrolysis in boiling water?

My parents claim they cannot pay for my college education; what are my options?

Arcane Tradition and Cost Efficiency: Learn spells on level-up, or learn them from scrolls/spellbooks?

Do legislators hold the right of legislative initiative?

What is wind "CALM"?

Can an open source licence be revoked if it violates employer's IP?

Sakkāya-Ditthi and Self-View

How to search for Android apps without ads?

Are athletes' college degrees discounted by employers and graduate school admissions?

How do I say what something is made out of?

How to remove multiple elements from Set/Map AND knowing which ones were removed?

Must a CPU have a GPU if the motherboard provides a display port (when there isn't any separate video card)?

Should I worry about having my credit pulled multiple times while car shopping?

What did the 8086 (and 8088) do upon encountering an illegal instruction?

Print the phrase "And she said, 'But that's his.'" using only the alphabet

mathrm in LaTeX

How can I count how many horizontal brush strokes are required to draw an array of buildings?

How would I fix my approach to this Manhattan Skyline/Stone Wall and where did I go wrong? JavascriptHow can I concatenate two arrays in Java?How can I create a two dimensional array in JavaScript?How can I add new array elements at the beginning of an array in Javascript?How can building a heap be O(n) time complexity?How can I access and process nested objects, arrays or JSON?How can I average an array of arrays in python?Linear time algorithm for slicing stacked boxesHighest value of last k values in array, better than O(n^2)Algorithm to detect duplication of integers in an unsorted array of n integers. (implemented with 2 nested loops)finding the least frequent number using two for loops?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;

22

3

By given an array of integers, each element represents a building. For example: int buildings[] = 1, 4, 3, 2, 3, 1.

If I drew the buildings horizontally with a brush, how many brush strike I would use?

I should write a function that returns the number of these brush strokes. For example 5.

I can do it easily on run time O(n^2), by using 2 loops.

• The external loop running on the levels of each building (according to the highest building).




• The inner loop is running on the array from 0 to n, and compares the difference of the height (0 or 1) between two near elements.

How can I do this in the O(n) time and O(n) space?

arrays algorithm

share|improve this question

edited May 30 at 18:11

Dukeling

45.8k1063110

asked May 30 at 7:23

Shir KShir K

1256

add a comment | 

22

3

By given an array of integers, each element represents a building. For example: int buildings[] = 1, 4, 3, 2, 3, 1.

If I drew the buildings horizontally with a brush, how many brush strike I would use?

I should write a function that returns the number of these brush strokes. For example 5.

I can do it easily on run time O(n^2), by using 2 loops.

• The external loop running on the levels of each building (according to the highest building).




• The inner loop is running on the array from 0 to n, and compares the difference of the height (0 or 1) between two near elements.

How can I do this in the O(n) time and O(n) space?

arrays algorithm

share|improve this question

edited May 30 at 18:11

Dukeling

45.8k1063110

asked May 30 at 7:23

Shir KShir K

1256

add a comment | 

By given an array of integers, each element represents a building. For example: int buildings[] = 1, 4, 3, 2, 3, 1.

If I drew the buildings horizontally with a brush, how many brush strike I would use?

I should write a function that returns the number of these brush strokes. For example 5.

I can do it easily on run time O(n^2), by using 2 loops.

• The external loop running on the levels of each building (according to the highest building).




• The inner loop is running on the array from 0 to n, and compares the difference of the height (0 or 1) between two near elements.

How can I do this in the O(n) time and O(n) space?

arrays algorithm

share|improve this question

edited May 30 at 18:11

Dukeling

45.8k1063110

asked May 30 at 7:23

Shir KShir K

1256

share|improve this question

edited May 30 at 18:11

Dukeling

45.8k1063110

asked May 30 at 7:23

Shir KShir K

1256

share|improve this question

edited May 30 at 18:11

Dukeling

45.8k1063110

asked May 30 at 7:23

Shir KShir K

1256

edited May 30 at 18:11

Dukeling

45.8k1063110

edited May 30 at 18:11

Dukeling

45.8k1063110

asked May 30 at 7:23

Shir KShir K

1256

asked May 30 at 7:23

Shir KShir K

1256

3 Answers
3

active

oldest

votes

15

A brush stroke starts whenever the height increases going from left to right, and ends when it decreases. You only need to look at when it increases, because if you just count the starting points of each stroke you will have the stroke count. Instead of looping over the height levels in an inner loop, just subtract one height level from the previous to get the difference.

In pseudo-code:

int BrushCount(int[] buildings)

 int brushCount = 0;
 int prevHeight = 0;
 for(int i = 0; i < buildings.length; i++)
 
 if(buildings[i] > prevHeight)
 brushCount = brushCount + (buildings[i] - prevHeight);
 prevHeight = buildings[i];
 
 return brushCount;

Runs in O(n).

share|improve this answer

edited May 31 at 0:09

answered May 30 at 7:36

samgaksamgak

19.5k33464

• 
  
  
  

  
  6
  

  
  
  
  
  
  

  
  
  Just a little nitpick - your pseudocode fails for the OP's two examples. Can you tell why?
  
  – גלעד ברקן
  May 30 at 14:14
  
  

  
  
  
  


• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  
  The update to prevHeight needs to happen unconditionally, otherwise the algorithm is incortect whenever you need multiple brush strokes on one height.
  
  – AlexR
  May 30 at 16:59
  

  
  
  
  

add a comment | 

2

A little code golf :) (Based on samgak's excellent explanation.)

const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));

console.log(f([1, 4, 3, 2, 3, 1]))
console.log(f([4, 1, 2, 1, 2, 2]))

share|improve this answer

answered May 30 at 14:48

גלעד ברקןגלעד ברקן

14.2k21646

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  
  Find actual code golf here.
  
  – Neil
  May 30 at 18:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Neil what makes mine not "actual?"
  
  – גלעד ברקן
  May 30 at 21:28
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Well you haven't even bothered to remove white space to reduce the byte count...
  
  – Neil
  May 30 at 23:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Code golf is about making code as short as possible. It's a fun game, but one that should never be used on code written for ones employer.
  
  – David Hammen
  May 30 at 23:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Neil that's only if you're planning to win the round. I maintain my line is code golf, albeit not the shortest.
  
  – גלעד ברקן
  May 31 at 0:56
  
  

  
  
  
  

add a comment | 

1

Counting from the end of the array use the last element as the initial value of the result, and compare the previous one with the current one.

If they are the same value then, the result increase one;
if the previous one is smaller than the current one, do nothing;
if the previous one is bigger than the current one then, result = result +previous-current

int i=sizeof buildings;
int t=buildings[i]; 
while(i>0)
 if(buildings[i-1]-buildings[i]>0) t+=(buildings[i-1]-buildings[i]);
 else if(buildings[i-1]-buildings[i]==0) ++t;
 --i;

return t;

share|improve this answer

edited May 30 at 7:49

answered May 30 at 7:40

ruobing xiaruobing xia

113

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f56373582%2fhow-can-i-count-how-many-horizontal-brush-strokes-are-required-to-draw-an-array%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

15

A brush stroke starts whenever the height increases going from left to right, and ends when it decreases. You only need to look at when it increases, because if you just count the starting points of each stroke you will have the stroke count. Instead of looping over the height levels in an inner loop, just subtract one height level from the previous to get the difference.

In pseudo-code:

int BrushCount(int[] buildings)

 int brushCount = 0;
 int prevHeight = 0;
 for(int i = 0; i < buildings.length; i++)
 
 if(buildings[i] > prevHeight)
 brushCount = brushCount + (buildings[i] - prevHeight);
 prevHeight = buildings[i];
 
 return brushCount;

Runs in O(n).

share|improve this answer

edited May 31 at 0:09

answered May 30 at 7:36

samgaksamgak

19.5k33464

• 
  
  
  

  
  6
  

  
  
  
  
  
  

  
  
  Just a little nitpick - your pseudocode fails for the OP's two examples. Can you tell why?
  
  – גלעד ברקן
  May 30 at 14:14
  
  

  
  
  
  


• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  
  The update to prevHeight needs to happen unconditionally, otherwise the algorithm is incortect whenever you need multiple brush strokes on one height.
  
  – AlexR
  May 30 at 16:59
  

  
  
  
  

add a comment | 

15

A brush stroke starts whenever the height increases going from left to right, and ends when it decreases. You only need to look at when it increases, because if you just count the starting points of each stroke you will have the stroke count. Instead of looping over the height levels in an inner loop, just subtract one height level from the previous to get the difference.

In pseudo-code:

int BrushCount(int[] buildings)

 int brushCount = 0;
 int prevHeight = 0;
 for(int i = 0; i < buildings.length; i++)
 
 if(buildings[i] > prevHeight)
 brushCount = brushCount + (buildings[i] - prevHeight);
 prevHeight = buildings[i];
 
 return brushCount;

Runs in O(n).

share|improve this answer

edited May 31 at 0:09

answered May 30 at 7:36

samgaksamgak

19.5k33464

• 
  
  
  

  
  6
  

  
  
  
  
  
  

  
  
  Just a little nitpick - your pseudocode fails for the OP's two examples. Can you tell why?
  
  – גלעד ברקן
  May 30 at 14:14
  
  

  
  
  
  


• 
  
  
  

  
  5
  

  
  
  
  
  
  

  
  
  The update to prevHeight needs to happen unconditionally, otherwise the algorithm is incortect whenever you need multiple brush strokes on one height.
  
  – AlexR
  May 30 at 16:59
  

  
  
  
  

add a comment | 

A brush stroke starts whenever the height increases going from left to right, and ends when it decreases. You only need to look at when it increases, because if you just count the starting points of each stroke you will have the stroke count. Instead of looping over the height levels in an inner loop, just subtract one height level from the previous to get the difference.

In pseudo-code:

int BrushCount(int[] buildings)

 int brushCount = 0;
 int prevHeight = 0;
 for(int i = 0; i < buildings.length; i++)
 
 if(buildings[i] > prevHeight)
 brushCount = brushCount + (buildings[i] - prevHeight);
 prevHeight = buildings[i];
 
 return brushCount;

Runs in O(n).

share|improve this answer

edited May 31 at 0:09

answered May 30 at 7:36

samgaksamgak

19.5k33464

int BrushCount(int[] buildings)

 int brushCount = 0;
 int prevHeight = 0;
 for(int i = 0; i < buildings.length; i++)
 
 if(buildings[i] > prevHeight)
 brushCount = brushCount + (buildings[i] - prevHeight);
 prevHeight = buildings[i];
 
 return brushCount;

share|improve this answer

edited May 31 at 0:09

answered May 30 at 7:36

samgaksamgak

19.5k33464

answered May 30 at 7:36

samgaksamgak

19.5k33464

answered May 30 at 7:36

samgaksamgak

19.5k33464

2

A little code golf :) (Based on samgak's excellent explanation.)

const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));

console.log(f([1, 4, 3, 2, 3, 1]))
console.log(f([4, 1, 2, 1, 2, 2]))

share|improve this answer

answered May 30 at 14:48

גלעד ברקןגלעד ברקן

14.2k21646

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  
  Find actual code golf here.
  
  – Neil
  May 30 at 18:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Neil what makes mine not "actual?"
  
  – גלעד ברקן
  May 30 at 21:28
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Well you haven't even bothered to remove white space to reduce the byte count...
  
  – Neil
  May 30 at 23:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Code golf is about making code as short as possible. It's a fun game, but one that should never be used on code written for ones employer.
  
  – David Hammen
  May 30 at 23:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Neil that's only if you're planning to win the round. I maintain my line is code golf, albeit not the shortest.
  
  – גלעד ברקן
  May 31 at 0:56
  
  

  
  
  
  

add a comment | 

2

A little code golf :) (Based on samgak's excellent explanation.)

const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));

console.log(f([1, 4, 3, 2, 3, 1]))
console.log(f([4, 1, 2, 1, 2, 2]))

share|improve this answer

answered May 30 at 14:48

גלעד ברקןגלעד ברקן

14.2k21646

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  
  Find actual code golf here.
  
  – Neil
  May 30 at 18:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Neil what makes mine not "actual?"
  
  – גלעד ברקן
  May 30 at 21:28
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Well you haven't even bothered to remove white space to reduce the byte count...
  
  – Neil
  May 30 at 23:08
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Code golf is about making code as short as possible. It's a fun game, but one that should never be used on code written for ones employer.
  
  – David Hammen
  May 30 at 23:12
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Neil that's only if you're planning to win the round. I maintain my line is code golf, albeit not the shortest.
  
  – גלעד ברקן
  May 31 at 0:56
  
  

  
  
  
  

add a comment | 

A little code golf :) (Based on samgak's excellent explanation.)

const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));

console.log(f([1, 4, 3, 2, 3, 1]))
console.log(f([4, 1, 2, 1, 2, 2]))

share|improve this answer

answered May 30 at 14:48

גלעד ברקןגלעד ברקן

14.2k21646

const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));

console.log(f([1, 4, 3, 2, 3, 1]))
console.log(f([4, 1, 2, 1, 2, 2]))

const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));

console.log(f([1, 4, 3, 2, 3, 1]))
console.log(f([4, 1, 2, 1, 2, 2]))

const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));

console.log(f([1, 4, 3, 2, 3, 1]))
console.log(f([4, 1, 2, 1, 2, 2]))

share|improve this answer

answered May 30 at 14:48

גלעד ברקןגלעד ברקן

14.2k21646

answered May 30 at 14:48

גלעד ברקןגלעד ברקן

14.2k21646

answered May 30 at 14:48

גלעד ברקןגלעד ברקן

14.2k21646

1

Counting from the end of the array use the last element as the initial value of the result, and compare the previous one with the current one.

If they are the same value then, the result increase one;
if the previous one is smaller than the current one, do nothing;
if the previous one is bigger than the current one then, result = result +previous-current

int i=sizeof buildings;
int t=buildings[i]; 
while(i>0)
 if(buildings[i-1]-buildings[i]>0) t+=(buildings[i-1]-buildings[i]);
 else if(buildings[i-1]-buildings[i]==0) ++t;
 --i;

return t;

share|improve this answer

edited May 30 at 7:49

answered May 30 at 7:40

ruobing xiaruobing xia

113

add a comment | 

1

Counting from the end of the array use the last element as the initial value of the result, and compare the previous one with the current one.

If they are the same value then, the result increase one;
if the previous one is smaller than the current one, do nothing;
if the previous one is bigger than the current one then, result = result +previous-current

int i=sizeof buildings;
int t=buildings[i]; 
while(i>0)
 if(buildings[i-1]-buildings[i]>0) t+=(buildings[i-1]-buildings[i]);
 else if(buildings[i-1]-buildings[i]==0) ++t;
 --i;

return t;

share|improve this answer

edited May 30 at 7:49

answered May 30 at 7:40

ruobing xiaruobing xia

113

add a comment | 

Counting from the end of the array use the last element as the initial value of the result, and compare the previous one with the current one.

If they are the same value then, the result increase one;
if the previous one is smaller than the current one, do nothing;
if the previous one is bigger than the current one then, result = result +previous-current

int i=sizeof buildings;
int t=buildings[i]; 
while(i>0)
 if(buildings[i-1]-buildings[i]>0) t+=(buildings[i-1]-buildings[i]);
 else if(buildings[i-1]-buildings[i]==0) ++t;
 --i;

return t;

share|improve this answer

edited May 30 at 7:49

answered May 30 at 7:40

ruobing xiaruobing xia

113

int i=sizeof buildings;
int t=buildings[i]; 
while(i>0)
 if(buildings[i-1]-buildings[i]>0) t+=(buildings[i-1]-buildings[i]);
 else if(buildings[i-1]-buildings[i]==0) ++t;
 --i;

return t;

share|improve this answer

edited May 30 at 7:49

answered May 30 at 7:40

ruobing xiaruobing xia

113

answered May 30 at 7:40

ruobing xiaruobing xia

113

answered May 30 at 7:40

ruobing xiaruobing xia

113