We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
An array would be less efficient as you would be needlessly processing the input multiple times (during the original read, writing to an array, processing the data in the array); because the data the problem requires you to process (the spaces falling within a diagonal) only needs to be processed once and follows a mathematical pattern, to use an array is inefficient as it results in extra processing cycles and a lot of unnecessary space blocked out (as well as unnecessary data stored) in your heap. It could also be argued that your use of multiplication (n * n) is inefficient (as opposed to using nested loops), because multiplication is a much more expensive process than addition.
If you are thinking about efficiency in terms of asymptotic notation, there is no real difference in efficiency as array and loop solutions for this problem both have the same asymptotic complexity (O(n)). If you're looking to learn more, I recommend "Algorithms Sequential & Parallel: A Unified Approach" 2nd edition by Russ Miller. He was by far my favorite professor, and it provides a really good high level overview of efficiency (don't get overwhelmed by the Math proofs, you can just skip over them and read the theory).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Diagonal Difference
You are viewing a single comment's thread. Return to all comments →
An array would be less efficient as you would be needlessly processing the input multiple times (during the original read, writing to an array, processing the data in the array); because the data the problem requires you to process (the spaces falling within a diagonal) only needs to be processed once and follows a mathematical pattern, to use an array is inefficient as it results in extra processing cycles and a lot of unnecessary space blocked out (as well as unnecessary data stored) in your heap. It could also be argued that your use of multiplication (n * n) is inefficient (as opposed to using nested loops), because multiplication is a much more expensive process than addition. If you are thinking about efficiency in terms of asymptotic notation, there is no real difference in efficiency as array and loop solutions for this problem both have the same asymptotic complexity (O(n)). If you're looking to learn more, I recommend "Algorithms Sequential & Parallel: A Unified Approach" 2nd edition by Russ Miller. He was by far my favorite professor, and it provides a really good high level overview of efficiency (don't get overwhelmed by the Math proofs, you can just skip over them and read the theory).