Given a string, $S$, of length $n$ and containing only characters in the set $\left\{\text{(}, \text{\{}, \text{[}, \text{)}, \text{\}}, \text{]}\right\}$, determine whether $S$ is balanced. A string of parentheses is said to be balanced iff.:
The approach is to use a stack in order to keep track of the state of our balance (and bracket types!) as we traverse $S$ linearly. Push each opening bracket onto the stack and pop each closing bracket off (only if it matches with the current top of the stack). If a closing bracket doesn't match with the current top of the stack (e.g., $\text{)}$ and $\text{\{}$), then the string is unbalanced. Once linear scan has terminated, if the stack is non-empty then the string is also unbalanced. If the stack is empty then the string is balanced.
#define STACKLEN 10000
bool isValid(char* s) {
if (s == NULL) return false;
size_t n = strlen(s);
size_t d = 0;
char stack[STACKLEN];
for (size_t i=0;i<n;i++) {
switch(s[i]) {
case '(':
case '{':
case '[':
stack[d] = s[i];
d++;
break;
case ')':
if (d > 0 && stack[d-1] == '(') {
d--;
} else {
return false;
}
break;
case '}':
if (d > 0 && stack[d-1] == '{') {
d--;
} else {
return false;
}
break;
case ']':
if (d > 0 && stack[d-1] == '[') {
d--;
} else {
return false;
}
break;
}
}
return d == 0;
}
Note: This is a Leetcode solution and, as such, makes use of an explicit bound on $n$ (i.e., 10000).
Given an array, $A$, of length $n$, that is sorted in non-decreasing order, produce the array, $A'$, of length $k$, that contains only the unique elements of $A$ in their original order.
int removeDuplicates(int* nums, int numsSize) {
if (nums == NULL || numsSize == 0) return 0;
if (numsSize == 1) return 1;
size_t pos = 0;
size_t arrlen = numsSize;
while (pos < arrlen - 1) {
if (nums[pos] == nums[pos+1]) {
for (size_t j=pos;j<arrlen-1;j++) {
nums[j] = nums[j+1];
}
arrlen--;
} else {
pos++;
}
}
return arrlen;
}
Note: This is a Leetcode solution and, as such, modifies the provided array (nums) by overwriting the duplicate elements as soon as they're encountered. The size of the resulting array is communicated via the returned value of the removeDuplicates function.
Given an array, $A$, of length $n$, and a value $x$, produce the array, $A'$, of length $k$, that contains all of the elements in $A$ such that $\forall i\leq k, A'\left[i\right]\neq x$.
Things to keep in mind:
int removeElement(int* nums, int numsSize, int val) {
if (nums == NULL || numsSize == 0) return 0;
size_t pos = 0;
size_t arrlen = numsSize;
while (pos < arrlen) {
if (nums[pos] == val) {
for (size_t j=pos;j<arrlen-1;j++) {
nums[j] = nums[j+1];
}
arrlen--;
} else {
pos++;
}
}
return arrlen;
}
Note: This is a Leetcode solution and, as such, modifies the input array (nums) in-place and communicates the length of the resultant array ($k$) via the return value.
Given two strings, $\text{haystack}$ of length $n$ and $\text{needle}$ of length $m\leq n$, compute the index into $\text{haystack}$ at which the first occurrence of $\text{needle}$ arises. If $\text{needle}$ does not occur within $\text{haystack}$ at all, return some sentinel value (usually $-1$).
Note that this is essentially strstr(3).
int strStr(char* haystack, char* needle) {
if (needle == NULL || haystack == NULL) return -1;
if (strlen(haystack) < strlen(needle)) return -1;
size_t n = strlen(haystack);
size_t m = strlen(needle);
for (size_t i=0;i<n;i++) {
for (size_t j=0;j<m;j++) {
if (haystack[i+j] != needle[j]) {
break;
} else if (j + 1 == m) {
return i;
}
}
}
return -1;
}
Given a string, $S$, determine the length of the last word in $S$. A word is a maximally-long substring of $S$, $s'$, that is delimited by whitespace (or the start or end of $S$). Usually this problem is presented in such a way that the number of words in $S$, $w\left(S\right)>0$. This obviously bounds the length of $S$, $n>0$ also.
int lengthOfLastWord(char* s) {
if (s == NULL) return -1;
if (strlen(s) == 1) return 1;
unsigned int w = 0;
bool in_word = false;
for (size_t i=strlen(s)-1;i>0;i--) {
if (in_word) {
if (s[i] == ' ') {
in_word = false;
return w;
} else {
w++;
}
} else {
if (s[i] != ' ') {
in_word = true;
w++;
}
}
}
if (s[0] != ' ') return w + 1;
else return w;
}
Note: This is a Leetcode solution and, as such, exploits the provided guarantee that there is at least one word within s.
Given an integer, $N\in\mathbb{N}$, represented as a sequence of its decimal digits $\overline{N}=\left\langle d_1, d_2, \dots, d_k\right\rangle$, compute $N+1$ as its decimal sequence, $\overline{N+1}$.
The complexity in this problem arise from the potential for arithmetic overflow. This will impact our algorithm in two ways:
#define MAX_DIGIT 9
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* plusOne(int* digits, int digitsSize, int* returnSize) {
if (digits == NULL || returnSize == NULL) return NULL;
if (digitsSize == 0) return NULL;
int* res = calloc(digitsSize + 1, sizeof(int));
if (res == NULL) return NULL;
*returnSize = digitsSize + 1;
bool overflow = false;
size_t i = digitsSize - 1;
do {
if (i == digitsSize - 1) {
if (digits[i] == MAX_DIGIT) {
res[i+1] = 0;
overflow = true;
} else {
res[i+1] = digits[i] + 1;
}
} else {
if (overflow) {
if (digits[i] == MAX_DIGIT) {
res[i+1] = 0;
} else {
res[i+1] = digits[i] + 1;
overflow = false;
}
} else {
res[i+1] = digits[i];
}
}
i--;
} while (i != SIZE_MAX);
if (overflow) {
/* the entire addition overflowed so add the new MSD */
res[0] = 1;
return res;
}
else {
/* we preallocated above so clip the array (this is a leak lol) */
*returnSize -= 1;
return res + 1;
}
}