Sorted Subsequence of Size 3 in C: O(n) Solution

Sorted Subsequence of Size 3 in C: A Comprehensive Tutorial

Given an array of n integers, the task is to find three elements arr[i] < arr[j] < arr[k] such that i < j < k in O(n) time. This classic problem tests your understanding of array traversal, auxiliary arrays, and the greedy technique for finding increasing subsequences.

This tutorial provides an in-depth exploration of finding a sorted subsequence of size 3 in C: naive auxiliary array approach, optimized single-pass approach, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Find three indices i < j < k such that arr[i] < arr[j] < arr[k]. If no such triplet exists, report that.

Examples:

text

Input: [12, 11, 10, 5, 6, 2, 30] Output: 5, 6, 30 Input: [1, 2, 3, 4] Output: 1, 2, 3 Input: [4, 3, 2, 1] Output: No such triplet exists.

Why This Problem Matters

• Greedy algorithm design: Demonstrates optimal substructure.
• Auxiliary arrays: Foundation for many array problems.
• Single-pass technique: Teaches efficient traversal.
• Interview preparation: Common coding interview question.
• Longest Increasing Subsequence (LIS): Foundation for LIS variants.

Key Insight

We need to find an element arr[j] that has:

• A smaller element on its left (arr[i] < arr[j])
• A larger element on its right (arr[j] < arr[k])

Approaches Overview

Approach	Time Complexity	Space Complexity
Auxiliary arrays	O(n)	O(n)
Single-pass greedy	O(n)	O(1)

---

Syntax & Core Mechanics

Approach 1: Auxiliary Arrays

Precompute smaller[i] (index of a smaller element on the left) and greater[i] (index of a greater element on the right).

c

#include <stdio.h> #include <stdlib.h> int findTriplet(const int arr[], int n, int *out) { if (n < 3) return 0; int *smaller = malloc(n * sizeof(int)); int *greater = malloc(n * sizeof(int)); if (smaller == NULL || greater == NULL) { free(smaller); free(greater); return 0; } /* smaller[i] = index of a smaller element on the left */ int minIdx = 0; smaller[0] = -1; for (int i = 1; i < n; i++) { if (arr[i] <= arr[minIdx]) { minIdx = i; smaller[i] = -1; } else { smaller[i] = minIdx; } } /* greater[i] = index of a greater element on the right */ int maxIdx = n - 1; greater[n - 1] = -1; for (int i = n - 2; i >= 0; i--) { if (arr[i] >= arr[maxIdx]) { maxIdx = i; greater[i] = -1; } else { greater[i] = maxIdx; } } /* Find index with both smaller and greater */ int found = 0; for (int i = 0; i < n; i++) { if (smaller[i] != -1 && greater[i] != -1) { out[0] = arr[smaller[i]]; out[1] = arr[i]; out[2] = arr[greater[i]]; found = 1; break; } } free(smaller); free(greater); return found; } int main(void) { int arr[] = {12, 11, 10, 5, 6, 2, 30}; int n = sizeof(arr) / sizeof(arr[0]); int result[3]; if (findTriplet(arr, n, result)) { printf("Triplet: %d, %d, %d\n", result[0], result[1], result[2]); } else { printf("No such triplet exists.\n"); } return 0; }

Expected output:

text

Triplet: 5, 6, 30

Time: O(n), Space: O(n)

Approach 2: Single-Pass Greedy (Optimal)

Track two smallest elements seen so far (first, second) and their predecessor (prevFirst). When a third element greater than second is found, return the triplet.

c

#include <stdio.h> #include <limits.h> int findTriplet(const int arr[], int n, int *out) { if (n < 3) return 0; int first = INT_MAX; int second = INT_MAX; int prevFirst = INT_MAX; for (int i = 0; i < n; i++) { int x = arr[i]; if (x <= first) { first = x; } else if (x <= second) { second = x; prevFirst = first; } else { out[0] = prevFirst; out[1] = second; out[2] = x; return 1; } } return 0; } int main(void) { int arr[] = {12, 11, 10, 5, 6, 2, 30}; int n = sizeof(arr) / sizeof(arr[0]); int result[3]; if (findTriplet(arr, n, result)) { printf("Triplet: %d, %d, %d\n", result[0], result[1], result[2]); } else { printf("No such triplet exists.\n"); } return 0; }

Expected output:

text

Triplet: 5, 6, 30

Time: O(n), Space: O(1)

Step-by-Step Trace for [12, 11, 10, 5, 6, 2, 30]

text

first = INF, second = INF, prevFirst = INF i=0, x=12: x <= first → first = 12 i=1, x=11: x <= first → first = 11 i=2, x=10: x <= first → first = 10 i=3, x=5: x <= first → first = 5 i=4, x=6: x <= second → second = 6, prevFirst = 5 i=5, x=2: x <= first → first = 2 (but second=6, prevFirst=5 still valid) i=6, x=30: x > second → return {prevFirst=5, second=6, x=30} ✓

Why prevFirst is Needed

When first gets updated to a smaller value, second still corresponds to a valid pair with the old first. prevFirst preserves that pairing.

text

Consider [3, 4, -1, 0, 2]: first=3, second=4, prevFirst=3 after i=1 i=2: x=-1 <= first → first=-1 i=3: x=0 <= second → second=0, prevFirst=-1 i=4: x=2 > second → return {-1, 0, 2} ✓

---

Full Practical Code Example with Explanation

This program demonstrates both approaches with verification, performance comparison, and edge cases.

Program: Sorted Subsequence of Size 3

c

/** * sorted_subsequence_3.c * Finds a sorted subsequence of size 3 in O(n) time. * Compares auxiliary array and single-pass greedy approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <limits.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int findTripletAux(const int arr[], int n, int *out); int findTripletGreedy(const int arr[], int n, int *out); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void printTriplet(const int *triplet); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Sorted Subsequence of Size 3 Finder ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate with Sample Arrays\n"); printf("2. Enter Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n; int triplet[3]; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nArray: "); printArray(arr, n); if (findTripletGreedy(arr, n, triplet)) { printf("Triplet: %d, %d, %d\n", triplet[0], triplet[1], triplet[2]); } else { printf("No such triplet exists.\n"); } break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Approach 1: Auxiliary arrays */ int findTripletAux(const int arr[], int n, int *out) { if (n < 3) return 0; int *smaller = malloc(n * sizeof(int)); int *greater = malloc(n * sizeof(int)); if (smaller == NULL || greater == NULL) { free(smaller); free(greater); return 0; } /* smaller[i] = index of smaller element on left */ int minIdx = 0; smaller[0] = -1; for (int i = 1; i < n; i++) { if (arr[i] <= arr[minIdx]) { minIdx = i; smaller[i] = -1; } else { smaller[i] = minIdx; } } /* greater[i] = index of greater element on right */ int maxIdx = n - 1; greater[n - 1] = -1; for (int i = n - 2; i >= 0; i--) { if (arr[i] >= arr[maxIdx]) { maxIdx = i; greater[i] = -1; } else { greater[i] = maxIdx; } } int found = 0; for (int i = 0; i < n; i++) { if (smaller[i] != -1 && greater[i] != -1) { out[0] = arr[smaller[i]]; out[1] = arr[i]; out[2] = arr[greater[i]]; found = 1; break; } } free(smaller); free(greater); return found; } /* Approach 2: Single-pass greedy */ int findTripletGreedy(const int arr[], int n, int *out) { if (n < 3) return 0; int first = INT_MAX; int second = INT_MAX; int prevFirst = INT_MAX; for (int i = 0; i < n; i++) { int x = arr[i]; if (x <= first) { first = x; } else if (x <= second) { second = x; prevFirst = first; } else { out[0] = prevFirst; out[1] = second; out[2] = x; return 1; } } return 0; } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Prints triplet */ void printTriplet(const int *triplet) { printf("(%d, %d, %d)\n", triplet[0], triplet[1], triplet[2]); } /* Demonstrates both approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {12, 11, 10, 5, 6, 2, 30}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int triplet[3]; printf("\nArray 1: "); printArray(arr1, n1); if (findTripletAux(arr1, n1, triplet)) { printf(" Aux: "); printTriplet(triplet); } if (findTripletGreedy(arr1, n1, triplet)) { printf(" Greedy: "); printTriplet(triplet); } int arr2[] = {1, 2, 3, 4}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); if (findTripletAux(arr2, n2, triplet)) { printf(" Aux: "); printTriplet(triplet); } if (findTripletGreedy(arr2, n2, triplet)) { printf(" Greedy: "); printTriplet(triplet); } int arr3[] = {4, 3, 2, 1}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3: "); printArray(arr3, n3); if (findTripletAux(arr3, n3, triplet)) { printf(" Aux: "); printTriplet(triplet); } else { printf(" Aux: No triplet\n"); } if (findTripletGreedy(arr3, n3, triplet)) { printf(" Greedy: "); printTriplet(triplet); } else { printf(" Greedy: No triplet\n"); } int arr4[] = {3, 4, -1, 0, 2}; int n4 = sizeof(arr4) / sizeof(arr4[0]); printf("\nArray 4: "); printArray(arr4, n4); if (findTripletGreedy(arr4, n4, triplet)) { printf(" Greedy: "); printTriplet(triplet); } } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000) ===\n"); int n = 100000; int *arr = malloc(n * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Increasing array with some shuffling */ srand(42); for (int i = 0; i < n; i++) { arr[i] = i + 1; } /* Shuffle slightly to make it non-trivial */ for (int i = 0; i < 100; i++) { int a = rand() % n; int b = rand() % n; int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } clock_t start, end; double timeTaken; int triplet[3]; start = clock(); int auxResult = findTripletAux(arr, n, triplet); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Aux (O(n) space): %s, Time = %.3f ms\n", auxResult ? "Found" : "Not found", timeTaken); start = clock(); int greedyResult = findTripletGreedy(arr, n, triplet); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Greedy (O(1) space): %s, Time = %.3f ms\n", greedyResult ? "Found" : "Not found", timeTaken); printf("\nVerification: %s\n", (auxResult == greedyResult) ? "PASS" : "FAIL"); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); int triplet[3]; /* Case 1: Empty array */ int arr1[] = {}; printf("Case 1: Empty array\n"); printf(" Result: %s\n", findTripletGreedy(arr1, 0, triplet) ? "Found" : "No triplet"); /* Case 2: Single element */ int arr2[] = {5}; printf("\nCase 2: Single element\n"); printf(" Array: "); printArray(arr2, 1); printf(" Result: %s\n", findTripletGreedy(arr2, 1, triplet) ? "Found" : "No triplet"); /* Case 3: Two elements */ int arr3[] = {1, 2}; printf("\nCase 3: Two elements\n"); printf(" Array: "); printArray(arr3, 2); printf(" Result: %s\n", findTripletGreedy(arr3, 2, triplet) ? "Found" : "No triplet"); /* Case 4: Exactly 3 increasing */ int arr4[] = {1, 2, 3}; printf("\nCase 4: Exactly 3 increasing\n"); printf(" Array: "); printArray(arr4, 3); if (findTripletGreedy(arr4, 3, triplet)) { printf(" Triplet: "); printTriplet(triplet); } /* Case 5: Decreasing */ int arr5[] = {5, 4, 3, 2, 1}; printf("\nCase 5: Decreasing\n"); printf(" Array: "); printArray(arr5, 5); printf(" Result: %s\n", findTripletGreedy(arr5, 5, triplet) ? "Found" : "No triplet"); /* Case 6: Equal elements */ int arr6[] = {2, 2, 2, 2}; printf("\nCase 6: Equal elements\n"); printf(" Array: "); printArray(arr6, 4); printf(" Result: %s\n", findTripletGreedy(arr6, 4, triplet) ? "Found" : "No triplet"); /* Case 7: Triplet at end */ int arr7[] = {9, 8, 7, 1, 2, 3}; printf("\nCase 7: Triplet at end\n"); printf(" Array: "); printArray(arr7, 6); if (findTripletGreedy(arr7, 6, triplet)) { printf(" Triplet: "); printTriplet(triplet); } /* Case 8: Negative numbers */ int arr8[] = {-5, -3, -1, -4, 0}; printf("\nCase 8: Negative numbers\n"); printf(" Array: "); printArray(arr8, 5); if (findTripletGreedy(arr8, 5, triplet)) { printf(" Triplet: "); printTriplet(triplet); } } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Auxiliary arrays: Precomputes smaller/greater for each index; O(n) time, O(n) space.
2. Single-pass greedy: Tracks first, second, and prevFirst; O(n) time, O(1) space.

Expected Output (sample run)

text

=== Sorted Subsequence of Size 3 Finder === --- Menu --- 1. Demonstrate with Sample Arrays 2. Enter Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [12, 11, 10, 5, 6, 2, 30] Aux: (5, 6, 30) Greedy: (5, 6, 30) Array 2: [1, 2, 3, 4] Aux: (1, 2, 3) Greedy: (1, 2, 3) Array 3: [4, 3, 2, 1] Aux: No triplet Greedy: No triplet Array 4: [3, 4, -1, 0, 2] Greedy: (-1, 0, 2) --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Empty array Result: No triplet Case 2: Single element Array: [5] Result: No triplet Case 3: Two elements Array: [1, 2] Result: No triplet Case 4: Exactly 3 increasing Array: [1, 2, 3] Triplet: (1, 2, 3) Case 5: Decreasing Array: [5, 4, 3, 2, 1] Result: No triplet Case 6: Equal elements Array: [2, 2, 2, 2] Result: No triplet Case 7: Triplet at end Array: [9, 8, 7, 1, 2, 3] Triplet: (1, 2, 3) Case 8: Negative numbers Array: [-5, -3, -1, -4, 0] Triplet: (-5, -3, -1)

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Confusing prevFirst with first

In the greedy approach, when first updates, prevFirst must retain the old value paired with second.

c

if (x <= first) { first = x; /* Don't overwrite prevFirst here */ } else if (x <= second) { second = x; prevFirst = first; /* Save old first */ }

2. Using < vs <=

The problem requires strictly increasing. Using <= allows equal elements, which breaks the requirement.

c

if (x <= first) first = x; /* Correct for strictly increasing */ else if (x <= second) second = x; else /* Triplet found */

3. Array Size Less Than 3

Return “no triplet” for n < 3.

c

if (n < 3) return 0;

4. Empty Array

No triplet possible.

5. All Equal Elements

No strictly increasing triplet; return no triplet.

c

int arr[] = {2, 2, 2, 2}; /* Result: No triplet */

6. Decreasing Array

No triplet possible.

c

int arr[] = {5, 4, 3, 2, 1}; /* Result: No triplet */

7. Negative Numbers

Works correctly with signed comparisons.

c

int arr[] = {-5, -3, -1, -4, 0}; /* Triplet: (-5, -3, -1) */

8. Integer Overflow with INT_MAX

Using INT_MAX as initial sentinel is safe for int values.

9. Memory Leaks in Auxiliary Approach

Free smaller and greater arrays.

c

free(smaller); free(greater);

10. Memory Considerations

• Auxiliary: O(n) extra space.
• Greedy: O(1) extra space — preferred.
• No dynamic allocation in greedy approach.
• Use int for elements; INT_MAX for sentinel.

---

Summary & Best Practices

Finding a sorted subsequence of size 3 in O(n) time is elegantly solved by the single-pass greedy approach. The auxiliary array approach is more intuitive but uses extra space.

Key Takeaways

• Find i < j < k with arr[i] < arr[j] < arr[k].
• Auxiliary: precompute smaller/greater; O(n) space.
• Greedy: track first, second, prevFirst; O(1) space.
• Use <= for updating first/second to enforce strict increase.
• prevFirst preserves the valid pair when first updates.
• Return any valid triplet; no need to find all.

Best Practices

1. Use the single-pass greedy approach for O(1) space.
2. Use INT_MAX sentinels for first and second.
3. Maintain prevFirst when updating first.
4. Use <= in comparisons to enforce strict increase.
5. Handle edge cases: n < 3, empty, all equal, decreasing.
6. Free auxiliary arrays in the O(n) space approach.
7. Test with negative numbers and mixed values.
8. Verify with both approaches during testing.
9. Document the greedy insight in comments.
10. Return early when triplet is found.

By mastering this problem, you’ll understand greedy single-pass techniques and be prepared for related problems like Longest Increasing Subsequence and increasing triplets.