'Finding peaks on C
Write C code to initialize an array of 10 integers. If both sides of a number are smaller than it, then that number is the peak. Once you have all the peaks, create an array, store all the peaks in this new array and print them. The first question is I do not know how many peaks it may have, how to create the array to store peaks?
#include <stdio.h>
int main(void) {
int vals[10] = {1,2,3,1,4,6,3,8,9,1}; // initialize an array of 10 integers
int length = sizeof(vals) / sizeof(vals[0]);
int peaks;
for (int i = 1； i < length-1; i++) {
if (vals[i] > vals[i-1] && vals[i+1]) { // If both sides of a number are smaller than it
peaks[i] = vals[i];
}
printf("%d",peaks[i]);
return 0;
}
Solution 1:[1]
Just create an array the same size as the vals array. It's guaranteed that the number of peaks cannot be larger than the number of values. In reality the former will be much smaller than the latter as not every value can be a peak(1).
But, allowing for ten will be more than enough, without too much wastage.
Then you just use a variable to dictate how many peaks there are. For example, initialise the peak array as:
int peak[10];
size_t num_peaks = 0;
To add a peak to that array:
peak[num_peaks++] = new_peak;
And to process the peaks:
for (size_t peak_idx = 0; peak_idx < num_peaks; ++peak_idx)
do_something_with(peak[peak_idx]);
And, a couple of things to keep in mind:
- Should you consider the first element to be a peak if the second is lower?
- Ditto for the final element if the penultimate one is lower.
- How do you handle plateaus (like
1, 3, 3, 2)? Neither of those3values are considered a peak under your current definition since the elements on either side are not both lower.
As a final suggestion, here is some Python code (you can convert it into C yourself, I tend to use Python as it's the ideal "pseudo-code" language) that will cater for what I believe is the best approach for finding peaks, by answering the questions above with:
- Yes, first element can be a peak.
- Yes, final element can also be a peak.
- With plateaus, you effectively compress them into a single value and follow the normal rules, so
1, 3, 3, 2is the same as1, 3, 2.
The basic idea is to track the changes in direction (or gradient) so that you only consider it a peak when you switch from increasing to decreasing gradient. That can be achieved with the following code:
import random
def peaks(my_list):
# Edge case, no peaks for empty list.
if len(my_list) == 0: return []
# Peak accumulation list.
# Would be array for C as per my suggestions above.
my_peaks = []
# Start by assuming we're increasing to allow first element peak.
prev = my_list[0]
direction = "up"
# Process every item in list.
for item in my_list:
# If switching from rising to falling, that was a peak.
if item < prev and direction == "up":
my_peaks.append(prev)
direction = "down"
# If switching from falling to rising, that was a trough.
# Prepare to detect next peak.
elif item > prev and direction == "down":
direction = "up"
# Plateaus make no changes.
# Store previous to detect peak/trough.
prev = item
# If rising at end, it's considered a final peak.
if direction == "up":
my_peaks.append(prev)
return my_peaks
# This is a test harness to check results.
def find_peaks(my_list):
print(f"List: {my_list}")
print(f" -> {peaks(my_list)}\n")
find_peaks([])
find_peaks([1])
find_peaks([1, 2, 3])
find_peaks([3, 2, 1])
find_peaks([1, 2, 3, 3, 3, 3, 3, 2])
find_peaks([10, 9, 9, 9, 9, 8, 9])
find_peaks([1, 2, 1, 2, 1, 2, 1, 2, 1, 2])
for attempt in range(10):
count = 5 + random.randint(0, 10)
find_peaks([random.randint(5, 30) for _ in range(count)])
Hopefully, you'll see how this works from the comments and the following test output (I've inserted v characters to indicate the relevant peaks):
List: []
-> []
v
List: [1]
-> [1]
v
List: [1, 2, 3]
-> [3]
v
List: [3, 2, 1]
-> [3]
v
List: [1, 2, 3, 3, 3, 3, 3, 2]
-> [3]
vv v
List: [10, 9, 9, 9, 9, 8, 9]
-> [10, 9]
v v v v v
List: [1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
-> [2, 2, 2, 2, 2]
vv vv vv vv
List: [30, 8, 7, 7, 29, 24, 15, 14, 7, 25, 17, 14, 27]
-> [30, 29, 25, 27]
vv vv vv vv
List: [10, 6, 16, 8, 18, 19, 25, 24, 18, 28]
-> [10, 16, 25, 28]
vv vv
List: [26, 13, 11, 13, 20, 17, 6, 6]
-> [26, 20]
vv vv vv vv vv
List: [17, 18, 30, 23, 14, 29, 17, 22, 22, 6, 15, 12, 11, 23]
-> [30, 29, 22, 15, 23]
vv vv vv
List: [26, 7, 16, 10, 23]
-> [26, 16, 23]
vv vv vv
List: [21, 12, 18, 14, 20]
-> [21, 18, 20]
vv vv vv
List: [27, 9, 13, 26, 15, 30]
-> [27, 26, 30]
vv vv vv
List: [11, 17, 21, 24, 26, 22, 16, 6, 7, 26, 16, 27]
-> [26, 26, 27]
vv vv vv vv
List: [12, 14, 9, 20, 21, 18, 6, 13, 10, 25, 5]
-> [14, 21, 13, 25]
vv vv
List: [17, 9, 30, 29, 7]
-> [17, 30]
This doesn't necessarily match your specific requirement that excludes the endpoints as possible peaks but that's fairly easy to adapt to by:
- Starting the main loop with the second element rather than the first; and
- Removing the final check for upward direction.
(1) The actual maximum number of peaks is about half the number of values, depending on how you define peak. With your current definition, the end points cannot be peaks since they have no values of the "other side" which can satisfy the "both sides of a number are smaller than it" requirement.
With the possibility that high values at the ends can be considered peaks, the maximum increases slightly.
With array sizes like ten, it's probably not worth worrying about the wastage of half the elements in the peaks array.
Solution 2:[2]
Once you have all the peaks, create an array...
Actually this implies a two-step approach. One pass to count the peaks, and a second to copy them into the new array.
At the same time it is misleading, because "having all the peaks" is not "determine the number of peaks".
Anyway, you can create an array at run-time with:
int *peaks = malloc(num_peaks * sizeof*peaks);
or simply as VLA:
int peaks[num_peaks];
(After obtaining num_peaks in a first run, in both cases)
On the other hand, this seems a bit complicated, since the first array has 10 integers by definition:
int length = sizeof(vals) / sizeof(vals[0]);
I would rather do this:
#define LENGTH = 10
int vals[LENGTH] = {1,2,3,1,4,
6,3,8,9,1};
Here vals is not a VLA, because LENGTH is turned into 10 at compile time.
Solution 3:[3]
you can use this function to find the index of peak in an array and then you can print accordingly.
Using Binary Search.
int findPeakElement(int* nums, int numsSize) {
if(numsSize<=1) return 0;
int left=0;int right=numsSize-1;
int mid;
while(left!=right){
if(nums[left]>nums[left+1]) {
right=left;break;
}
else left+=1;
if(nums[right]>nums[right-1]){
left=right;break;
}
else right-=1;
mid=(right-left)/2+left;
if(nums[mid]<nums[mid+1])left=mid+1;
else right=mid;
}
return left;
}
Solution 4:[4]
You were so close. You set you loop limits correctly to allow you to check both sides of the current index in the vals[] array. By looping from 1 to length - 1 you can check the values at vals[i-1] and vals[i+1] each iteration. Neither end value can be a peak as there is no value on the opposite side to check.
However, after setting up your loop, you didn't check each side of vals[i] to determine if the current value was a peak. You need to do:
/* loop from 1 to length-1 checking value each side of current index */
for (int i = 1; i < length - 1; i++) {
if (vals[i-1] < vals[i] && vals[i] > vals[i+1]) { /* if peak */
...
Once you determine it is a peak, simply add vals[i] as the next element in the peaks[] array, e.g.
...
if (vals[i-1] < vals[i] && vals[i] > vals[i+1]) { /* if peak */
peaks[npeaks] = vals[i]; /* add value to peaks array */
npeaks += 1; /* increment no. of peaks */
}
}
A short example showing the complete program would be:
#include <stdio.h>
int main (void) {
int vals[] = {1,2,3,1,4,6,3,8,9,1},
length = sizeof vals / sizeof *vals,
peaks[sizeof vals] = {0}, /* create peaks array */
npeaks = 0; /* no. of peaks found */
/* loop from 1 to length-1 checking value each side of current index */
for (int i = 1; i < length - 1; i++) {
if (vals[i-1] < vals[i] && vals[i] > vals[i+1]) { /* if peak */
peaks[npeaks] = vals[i]; /* add value to peaks array */
npeaks += 1; /* increment no. of peaks */
}
}
puts ("peaks:"); /* output result */
for (int i = 0; i < npeaks; i++) {
printf (" peaks[%d] : %d\n", i, peaks[i]);
}
}
(note: when using sizeof with an expression, it is generally just sizeof expression, when using with a type (such as int), then it is generally sizeof(type), but note compilers will generally accept either sizeof(expression) or sizeof(type), but not sizeof type. See C11 Standard - 6.5.3 Unary operators)
Example Use/Output
$ ./bin/arrpeaks
peaks:
peaks[0] : 3
peaks[1] : 6
peaks[2] : 9
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 | neslrac |
| Solution 3 | Manishyadav |
| Solution 4 |