Evaluating Pattern Selection Criteria

function analyzeTradeoffs() {
  const patterns = [
    { name: "Brute Force", time: "O(n^k)", space: "O(1)" },
    { name: "Divide & Conquer", time: "O(n log n)", space: "O(log n)" },
    { name: "Dynamic Programming", time: "O(n^2)", space: "O(n)" },
    { name: "Greedy Algorithm", time: "O(n log n)", space: "O(1)" },
    { name: "Backtracking", time: "O(k^n)", space: "O(n)" }
  ];

  patterns.forEach(pattern => {
    console.log(`${pattern.name}: ${pattern.time} / ${pattern.space}`);
  });
}

const processData = (data) => {
  const validated = validate(data);
  const transformed = transform(validated);
  const normalized = normalize(transformed);
  return normalized;
};

const inputSize = 10000;
let pattern;

if (inputSize > 10000) {
  pattern = "Divide and Conquer";
} else if (inputSize > 1000) {
  pattern = "Dynamic Programming";
} else if (inputSize > 100) {
  pattern = "Greedy Algorithm";
} else {
  pattern = "Brute Force";
}

console.log("Recommended pattern:", pattern); // Output: Divide and Conquer

// Brute Force - O(2^n)
function bruteForceSubsetSum(arr, target) {
  const result = [];
  const n = arr.length;
  for (let i = 0; i < (1 << n); i++) {
    let sum = 0;
    for (let j = 0; j < n; j++) {
      if ((i & (1 << j)) !== 0) sum += arr[j];
    }
    if (sum === target) result.push(i);
  }
  return result;
}

// Divide and Conquer - O(n log n)
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Dynamic Programming - O(n^2)
function longestCommonSubsequence(str1, str2) {
  const dp = Array(str1.length + 1).fill().map(() => Array(str2.length + 1).fill(0));
  for (let i = 1; i <= str1.length; i++) {
    for (let j = 1; j <= str2.length; j++) {
      if (str1[i - 1] === str2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[str1.length][str2.length];
}

// Brute Force - O(1) space
function bruteForce(arr) {
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

// Dynamic Programming - O(n) space
function dpMax(arr) {
    const dp = new Array(arr.length);
    dp[0] = arr[0];
    for (let i = 1; i < arr.length; i++) {
        dp[i] = Math.max(arr[i], dp[i-1] + arr[i]);
    }
    return Math.max(...dp);
}

// Linear search for small dataset
const data = [5, 2, 8, 1, 9];
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// Binary search for large sorted dataset
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

class SortStrategy {
  sort(data) { throw new Error("Not implemented"); }
}

class BubbleSort extends SortStrategy {
  sort(data) { return data.sort(); }
}

class MergeSort extends SortStrategy {
  sort(data) { return this.mergeSort(data); }
}

class DataObserver {
  constructor() {
    this.observers = [];
  }

  notify(data) {
    this.observers.forEach(observer => observer.update(data));
  }

  subscribe(observer) {
    this.observers.push(observer);
  }
}

class SortableData extends DataObserver {
  constructor(strategy = new BubbleSort()) {
    super();
    this.strategy = strategy;
  }

  setStrategy(strategy) {
    this.strategy = strategy;
  }

  processData(data) {
    const sorted = this.strategy.sort(data);
    this.notify(sorted);
    return sorted;
  }
}

// Usage
const data = [3, 1, 4, 1, 5];
const observer = {
  update: (sorted) => console.log("Sorted data:", sorted)
};

const sortable = new SortableData(new MergeSort());
sortable.subscribe(observer);
sortable.processData(data);

// Inefficient O(n^2) approach
function findDuplicates(arr) {
  const duplicates = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        duplicates.push(arr[i]);
      }
    }
  }
  return duplicates;
}

// Efficient O(n) approach using Set
function findDuplicatesOptimized(arr) {
  const seen = new Set();
  const duplicates = new Set();
  for (let i = 0; i < arr.length; i++) {
    if (seen.has(arr[i])) {
      duplicates.add(arr[i]);
    } else {
      seen.add(arr[i]);
    }
  }
  return Array.from(duplicates);
}

const patterns = [
  { name: "Divide and Conquer", complexity: "O(log n)", useCase: "Sorting, searching" },
  { name: "Dynamic Programming", complexity: "O(n^2)", useCase: "Optimization problems" },
  { name: "Greedy Algorithm", complexity: "O(n)", useCase: "Activity selection" }
];

function selectOptimalPattern(patterns) {
  return patterns.reduce((best, current) => {
    if (current.complexity < best.complexity) return current;
    return best;
  });
}

const optimal = selectOptimalPattern(patterns);
console.log("Selected pattern:", optimal.name);